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 >>>

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 >>>