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
Published in SODA 2015, 2015
with Mark Braverman and Omri Weinstein
Download here
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
Published in EC 2016, 2016
with Umang Bhaskar, Yu Cheng and Chaitanya Swamy
Download here
Published in SODA 2017, 2017
with Mark Braverman, Aviad Rubinstein and Omri Weinstein
Download here
Published in ITCS 2018, 2018
with Mark Braverman
Download here
Published in APPROX/RANDOM 2018, 2018
with Mark Braverman
Download here
Published in FOCS 2020, 2019
with Omri Weinstein
Download here
Published:
Theory Lunch Talk on ETH-based Computational Lower Bound for finding Good Nash Equilibria in two player game.
Published:
Conference Version of Nash Equilibrium Lower Bound Result.
Published:
Conference Version of Information Value of the Game.
Published:
Conference Version of Semi-Direct Sum Result
Published:
In 2010, Patrascu proposed the Multiphase problem as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures, and showed it would imply unconditional lower bounds on many important dynamic data structure problems. After 10 years, there has been almost no progress on this conjecture. We show an ~\Omega(\sqrt{n}) cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but “layered” adaptivity. This captures all known set-intersection data structures and significantly strengthens previous Multiphase lower bounds, which only captured non-adaptive data structures. Our main technical result is a communication lower bound on a 4-party variant of Patrascu’s Number-On-Forehead game, using information complexity techniques.
Undergraduate course, NYU, Courant, 2018
2018 Fall Data Structure course
Undergraduate course, NYU, Courant, 2019
2019 Spring Data Structure course
Undergraduate course, NYU, Courant, 2019
2019 Fall Data Structure course