Research interests: Theory of Computation, in a broad sense. Main focus is "Fine-Grained Complexity" aiming to understand the exact computational complexity of basic and fundamental problems. Other topics include: Graph Theory and Algorithms, Dynamic Data Structures, Pattern Matching and Sequence Alignment, Exact Algorithms and Parameterized Complexity, Distributed Computing, and Circuit Complexity.
Current position: Senior Scientist, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science.
Previously: IBM Almaden Research Center (Research Staff Member), Stanford University (Ph.D.), Technion (M.Sc.), University of Haifa (B.Sc. via the "Etgar" program).
Publications: Google Scholar, DBLP, partial list with summaries.
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs; with Krauthgamer and Trabelsi STOC'21. [arxiv]
Distributed PCP Theorems and Hardness of Approximation in P; with Rubinstein and Williams FOCS'17. [arxiv]
- If the Current Clique Algorithms are Optimal, so is Valiant's Parser; with Backurs and Vassilevska Williams FOCS'15. [slides] [pdf]
- Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems; with Vassilevska Williams FOCS'14. [slides] [pdf]
FOCS 2023, ICALP 2023, STOC 2023, SWAT 2022, SODA 2022, SOSA 2022, ESA 2020, CPM 2020, IPEC 2019, STOC 2019, FOCS 2018, CPM 2016