Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-092 | 2nd June 2011 09:44

Memory-Restricted Black-Box Complexity

RSS-Feed




TR11-092
Authors: Doerr Benjamin, Winzen Carola
Publication: 14th June 2011 14:04
Downloads: 1415
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint