Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kord Eickmeyer:

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

TR10-056 | 1st April 2010
Kord Eickmeyer, Martin Grohe

Randomisation and Derandomisation in Descriptive Complexity Theory

Revisions: 1

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ... more >>>

ISSN 1433-8092 | Imprint