1.8k citations
- Tel Aviv UniversityIL45 papers
- Boston UniversityUS31 papers
- Ben-Gurion University of the NegevIL26 papers
- Technion – Israel Institute of TechnologyIL26 papers
- Ariel UniversityIL22 papers
- Hebrew University of JerusalemIL22 papers
- University of Maryland, College ParkUS21 papers
- Weizmann Institute of ScienceIL19 papers
- Centre National de la Recherche ScientifiqueFR18 papers
- Harvard UniversityUS16 papers
- Institute of MathematicsPL13 papers
- Institute of Radio AstronomyUA13 papers
5 papers · 2 filters
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…