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
7 papers · 2 filters
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…
The streaming -mismatch problem
Raphaël Clifford, Tomasz Kociumaka, Ely Porat
We consider the streaming complexity of a fundamental task in approximate pattern matching: the -mismatch problem. It asks to compute Hamming distances between a pattern of leng…
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta +1
We study the problem of embedding shortest-path metrics of weighted graphs into spaces. We introduce a new embedding technique based on low-depth decompositions of a graph…
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…
Streaming Pattern Matching with d Wildcards
Shay Golan, Tsvi Kopelowitz, Ely Porat
In the pattern matching with wildcards problem one is given a text of length and a pattern of length that contains wildcard characters, each denoted by a sp…
Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interac…