Publications

An Ω( (log n / log log n)^2 ) Cell-Probe Lower Bound for Dynamic Boolean Data Structures

Published in FOCS 2026 (to appear)

Download here

An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks

Published in FOCS 2020

with Omri Weinstein

Download here

Semi-Direct Sum Theorem and Nearest Neighbor under l infinity

Published in APPROX/RANDOM 2018

with Mark Braverman

Download here

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

Published in FOCS 2015, QIP 2016, Invited to SIAM Journal on Computing

with Mark Braverman, Ankit Garg, Jieming Mao and Dave Touchette

Download here

CAMP: Coreset Accelerated Metacell Partitioning enables scalable analysis of single-cell data

Published in RECOMB 2026 (bioinformatics)

with Danrong Li and Stefan Canzar

Download here

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Published in ICALP 2026

with Jeremy Ahrens Huang and Chunhao Wang

Download here

Information Value of the Game

Published in ITCS 2018

with Mark Braverman

Download here

ETH Hardness for Densest-k-Subgraph with Perfect Completeness

Published in SODA 2017

with Mark Braverman, Aviad Rubinstein and Omri Weinstein

Download here

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Published in EC 2016

with Umang Bhaskar, Yu Cheng and Chaitanya Swamy

Download here

Approximating the best Nash Equilibrium in sub quasipolytime breaks the Exponential Time Hypothesis

Published in SODA 2015

with Mark Braverman and Omri Weinstein

Download here