4 citations · 10 across the 14 of their papers we have counts for
7 papers · 1 filter
Exponential Communication Separations between Notions of Selfishness
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas +2
We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type from each player and outputs an outcome $f(t_…
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…
Communication complexity of Nash equilibrium in potential games
Yakov Babichenko, Aviad Rubinstein
We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires c…
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…
A Simple Sublinear Algorithm for Gap Edit Distance
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
We study the problem of estimating the edit distance between two -character strings. While exact computation in the worst case is believed to require near-quadratic time, previo…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…