13 citations · 17 across the 6 of their papers we have counts for
8 papers · 1 filter
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…
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…