Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR09-070 | 1st September 2009
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Pseudorandomness for Width 2 Branching Programs

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

ISSN 1433-8092 | Imprint