2 citations · 2 across the 5 of their papers we have counts for
5 papers
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…
Weighted ancestors in suffix trees
Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson
The classical, ubiquitous, predecessor problem is to construct a data structure for a set of integers that supports fast predecessor queries. Its generalization to weighted trees,…
Fast, precise and dynamic distance queries
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz +2
We present an approximate distance oracle for a point set S with n points and doubling dimension λ. For every ε>0, the oracle supports (1+ε)-approximate distance queries in (univer…
Restricted Common Superstring and Restricted Common Supersequence
Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein +1
The {\em shortest common superstring} and the {\em shortest common supersequence} are two well studied problems having a wide range of applications. In this paper we consider both…