13 citations · 37 across the 16 of their papers we have counts for
20 papers
Set Parameterized Matching via Multi-Layer Hashing
Moshe Lewenstein, Ely Porat
We study the "set parameterized matching" problem, a generalization of the classical parameterized matching problem introduced by Baker. In set parameterized matching, both the pat…
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3
In Gapped String Indexing, the goal is to compactly represent a string of length such that for any query consisting of two strings and , called patterns, and an…
On the Hardness of Set Disjointness and Set Intersection with Bounded Universe
Isaac Goldstein, Moshe Lewenstein, Ely Porat
In the SetDisjointness problem, a collection of sets from some universe is preprocessed in order to answer queries on the emptiness of the intersection of…
Improved Space-Time Tradeoffs for kSUM
Isaac Goldstein, Moshe Lewenstein, Ely Porat
In the kSUM problem we are given an array of numbers and we are required to determine if there are different elements in this array such that their sum is 0.…
Orthogonal Vectors Indexing
Isaac Goldstein, Moshe Lewenstein, Ely Porat
In the recent years, intensive research work has been dedicated to prove conditional lower bounds in order to reveal the inner structure of the class P. These conditional lower bou…
Conditional Lower Bounds for Space/Time Tradeoffs
Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein +1
In recent years much effort has been concentrated towards achieving polynomial time lower bounds on algorithms for solving various well-known problems. A useful technique for showi…
How Hard is it to Find (Honest) Witnesses?
Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein +1
In recent years much effort was put into developing polynomial-time conditional lower bounds for algorithms and data structures in both static and dynamic settings. Along these lin…
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…
Beyond the Runs Theorem
Johannes Fischer, Štěpán Holub, Tomohiro I +1
Recently, a short and elegant proof was presented showing that a binary word of length contains at most runs. Here we show, using the same technique and a computer search…
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,…
On Hardness of Jumbled Indexing
Amihood Amir, Timothy Chan, Moshe Lewenstein +1
Jumbled indexing is the problem of indexing a text for queries that ask whether there is a substring of matching a pattern represented as a Parikh vector, i.e., the vector…
Space-Efficient String Indexing for Wildcard Pattern Matching
Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter
In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n\log^{\varep…
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein
Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially size…
Finding the Minimum-Weight k-Path
Avinatan Hassidim, Orgad Keller, Moshe Lewenstein +1
Given a weighted -vertex graph with integer edge-weights taken from a range , we show that the minimum-weight simple path visiting vertices can be found in time…
Succinct data structures for representing equivalence classes
Moshe Lewenstein, J. Ian Munro, Venkatesh Raman
Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are i…
Orthogonal Range Searching for Text Indexing
Moshe Lewenstein
Text indexing, the problem in which one desires to preprocess a (usually large) text for future (shorter) queries, has been researched ever since the suffix tree was invented in th…
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing
Amihood Amir, Gianni Franceschini, Roberto Grossi +3
This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data…
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…