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
11 papers · 2 filters
Polynomials: a new tool for length reduction in binary discrete convolutions
Amihood Amir, Oren Kapah, Ely Porat +1
Efficient handling of sparse data is a key challenge in Computer Science. Binary convolutions, such as polynomial multiplication or the Walsh Transform are a useful tool in many ap…
Improved Algorithms for Parity and Streett objectives
Krishnendu Chatterjee, Monika Henzinger, Veronika Loitzenbauer
The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with ap…
Dictionary Matching with One Gap
Amihood Amir, Avivit Levy, Ely Porat +1
The dictionary matching with gaps problem is to preprocess a dictionary of gapped patterns over alphabet , where each gapped pattern is a sequence…
The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets
Amihood Amir, Oren Kapah, Tsvi Kopelowitz +2
We introduce and examine the {\em Holiday Gathering Problem} which models the difficulty that couples have when trying to decide with which parents should they spend the holiday. O…
New routing techniques and their applications
Liam Roditty, Roei Tov
Let be an undirected graph with vertices and edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $\tilde O(\fra…
Higher Lower Bounds from the 3SUM Conjecture
Tsvi Kopelowitz, Seth Pettie, Ely Porat
The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pǎtraşcu…
Dynamic Set Intersection
Tsvi Kopelowitz, Seth Pettie, Ely Porat
Consider the problem of maintaining a family of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given , report every member of…
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…
For-all Sparse Recovery in Near-Optimal Time
Anna C. Gilbert, Yi Li, Ely Porat +1
An approximate sparse recovery system in norm consists of parameters , , , an -by- measurement , and a recovery algorithm, . Given a 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…