4 citations · 10 across the 11 of their papers we have counts for
7 papers · 1 filter
Settling the complexity of Nash equilibrium in congestion games
Yakov Babichenko, Aviad Rubinstein
We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and (ii) the problem of finding an (exponential precision) fixed point of the gradie…
The Strongish Planted Clique Hypothesis and Its Consequences
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time (so…
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Mika Göös, Aviad Rubinstein
We prove an lower bound on the randomized communication complexity of finding an -approximate Nash equilibrium (for constant ) in a two-player game…
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless th…
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment to a CNF formula is shared between two parties, where…
Inapproximability of VC Dimension and Littlestone's Dimension
Pasin Manurangsi, Aviad Rubinstein
We study the complexity of computing the VC Dimension and Littlestone's Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x…