Home

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).

 
Selected papers:

  • Gomory-Hu Tree in Subcubic Time; with Krauthgamer, Li, Panigrahi, Saranurak, and Trabelsi FOCS'22. [arxiv] [slides] [video]

  • 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]
  • The 4/3 Additive Spanner Exponent is Tight; with Bodwin  STOC'16.  [arxiv] [slides]
  • Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made; with Hansen, Vassilevska Williams, and Williams  STOC'16.  [pdf] [video] [slides]
  • 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]
 
PC member: 
FOCS 2023, ICALP 2023, STOC 2023, SWAT 2022, SODA 2022, SOSA 2022, ESA 2020, CPM 2020, IPEC 2019, STOC 2019, FOCS 2018, CPM 2016