All reports by Author Elad Verbin:

__
TR12-025
| 23rd March 2012
__

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin#### Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than $\xi/2$, where $\xi = \frac{3-\sqrt5}{2} \approx 0.382$, is not possible by a polynomial time algorithm. ... more >>>

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>