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
74 papers · 1 filter
On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and -Mismatches
Amihood Amir, Ayelet Butman, Michael Itzhaki +1
This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classi…
Multiway Cuts with a Choice of Representatives
Kristóf Bérczi, Tamás Király, Daniel P. Szabo
In this paper, we study several generalizations of multiway cut where the terminals can be chosen as \emph{representatives} from sets of \emph{candidates} . In this…
Optimal Padded Decomposition For Bounded Treewidth Graphs
Arnold Filtser, Tobias Friedrich, Davis Issac +4
A -padded decomposition of an edge-weighted graph is a stochastic decomposition into clusters of diameter at most such that for every vertex , th…
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
We consider the well-studied Robust -Clustering problem, which generalizes the classic -Median, -Means, and -Center problems. Given a constant , the input…
A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
Eyal Weiss, Ariel Felner, Gal A. Kaminka
The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized fram…
An Improved Algorithm for The -Dyck Edit Distance Problem
Dvir Fried, Shay Golan, Tomasz Kociumaka +3
A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses is the smallest…
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Private Approximations of a Convex Hull in Low Dimensions
Yue Gao, Or Sheffet
We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull,…
Update Query Time Trade-off for dynamic Suffix Arrays
Amihood Amir, Itai Boneh
The Suffix Array SA(S) of a string S[1 ... n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing da…
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Tomasz Kociumaka, Barna Saha
In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance prob…
Weighted Adaptive Coding
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein +1
Huffman coding is known to be optimal, yet its dynamic version may be even more efficient in practice. A new variant of Huffman encoding has been proposed recently, that provably a…
Time-Space Tradeoffs for Finding a Long Common Substring
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka +1
We consider the problem of finding, given two documents of total length , a longest string occurring as a substring of both documents. This problem, known as the Longest Common…
A Framework for Adversarially Robust Streaming Algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff +1
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chose…
Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
The classical problem of degree sequence realizability asks whether or not a given sequence of positive integers is equal to the degree sequence of some -vertex undirected s…
Resolution of the Burrows-Wheeler Transform Conjecture
Dominik Kempa, Tomasz Kociumaka
The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main com…
Noisy Beeping Networks
Yagel Ashkenazi, Ran Gelles, Amir Leshem
We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfecti…
The Strong 3SUM-INDEXING Conjecture is False
Tsvi Kopelowitz, Ely Porat
In the 3SUM-Indexing problem the goal is to preprocess two lists of elements from , and , such that given an element one c…
Cartesian Tree Matching and Indexing
Sung Gwan Park, Amihood Amir, Gad M. Landau +1
We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we d…
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa, Tomasz Kociumaka
Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text of length , permutes its symbols according to the lexicographic order of suffixes of…
Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
Ran Gelles, Yael T. Kalai, Govind Ramnarayan
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop…
Locally Consistent Parsing for Text Indexing in Small Space
Or Birenzwige, Shay Golan, Ely Porat
We consider two closely related problems of text indexing in a sub-linear working space. The first problem is the Sparse Suffix Tree (SST) construction of a set of suffixes usi…
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal +2
Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter ex…
Optimal Short-Circuit Resilient Formulas
Mark Braverman, Klim Efremenko, Ran Gelles +1
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) convert…
Constructing Light Spanners Deterministically in Near-Linear Time
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser +2
Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [CW18] improved the state-of-the-art for light spann…