Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MEMORY RESTRICTION:
Reports tagged with memory restriction:
TR11-092 | 2nd June 2011
Doerr Benjamin, Winzen Carola

Memory-Restricted Black-Box Complexity

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



ISSN 1433-8092 | Imprint