4.5k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Tel Aviv UniversityIL181 papers
- Boston UniversityUS130 papers
- Weizmann Institute of ScienceIL117 papers
- Ariel UniversityIL101 papers
- Ben-Gurion University of the NegevIL99 papers
- Centre National de la Recherche ScientifiqueFR98 papers
- Hebrew University of JerusalemIL95 papers
- Technion – Israel Institute of TechnologyIL90 papers
- Massachusetts Institute of TechnologyUS82 papers
- Stanford UniversityUS75 papers
- University of CambridgeGB70 papers
- University of Maryland, College ParkUS68 papers
7 papers · 2 filters
Waste Makes Haste: Bounded Time Protocols for Envy-Free Cake Cutting with Free Disposal
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann
We consider the classic problem of envy-free division of a heterogeneous good ("cake") among several agents. It is known that, when the allotted pieces must be connected, the probl…
The k-mismatch problem revisited
Raphaël Clifford, Allyx Fontaine, Ely Porat +2
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and ev…
Distance labeling schemes for trees
Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen +1
We consider distance labeling schemes for trees: given a tree with nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, b…
Dictionary matching in a stream
Raphael Clifford, Allyx Fontaine, Ely Porat +2
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan, Moshe Lewenstein
We present a collection of new results on problems related to 3SUM, including: 1. The first truly subquadratic algorithm for 1a. computing the (min,+) convolution for…
Sorting and Selection with Imprecise Comparisons
Miklos Ajtai, Vitaly Feldman, Avinatan Hassidim +1
We consider a simple model of imprecise comparisons: there exists some such that when a subject is given two elements to compare, if the values of those elements (as perceive…