All reports by Author Aviad Rubinstein:

__
TR15-093
| 5th June 2015
__

Aviad Rubinstein#### Inapproximability of Nash Equilibrium

__
TR15-074
| 29th April 2015
__

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

Aviad Rubinstein

We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions.

As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete ... more >>>

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>