Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with games:
TR13-136 | 27th September 2013
Paul Goldberg, Aaron Roth

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>

TR14-016 | 16th January 2014
Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

The Complexity of Debate Checking

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

TR22-134 | 23rd September 2022
Greg McLellan, Alexey Milovanov

Some Games on Turing Machines and Power from Random Strings

Revisions: 1

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ... more >>>

ISSN 1433-8092 | Imprint