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 Researcher, 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:
  • 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]

 

Helpful resources on "Hardness in P": 

 
PC member: 
SODA 2022, SOSA 2022, ESA 2020CPM 2020IPEC 2019STOC 2019FOCS 2018CPM 2016