An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks
Published in FOCS 2020, 2019
with Omri Weinstein
Download here
Publications
Semi-Direct Sum Theorem and Nearest Neighbor under l infinity
Published in APPROX/RANDOM 2018, 2018
with Mark Braverman
Download here
Information Value of the Game
Published in ITCS 2018, 2018
with Mark Braverman
Download here
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
Published in SODA 2017, 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, 2016
with Umang Bhaskar, Yu Cheng and Chaitanya Swamy
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, 2015
with Mark Braverman, Ankit Garg, Jieming Mao and Dave Touchette
Download here
Approximating the best Nash Equilibrium in sub quasipolytime breaks the Exponential Time Hypothesis
Published in SODA 2015, 2015
with Mark Braverman and Omri Weinstein
Download here