All reports by Author Doerr Benjamin:

__
TR12-087
| 4th July 2012
__

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

__
TR11-092
| 2nd June 2011
__

Doerr Benjamin, Winzen Carola#### Memory-Restricted Black-Box Complexity

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Doerr Benjamin, Winzen Carola

We show that the black-box complexity with memory restriction one of the $n$-dimensional $\onemax$ function class is at most $2n$. This disproves the $\Theta(n \log n)$ conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544).

more >>>