Campus Event Calendar

Event Entry

What and Who

Another Game People Don't Play or The Black-Box Complexity of the LeadingOnes Class

Benjamin Doerr
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI  
AG Audience

Date, Time and Location

Tuesday, 15 November 2011
30 Minutes
E1 4


Lets play the following game: I choose a bit-string z of length n and a permutation \sigma of the first n numbers. Both are unknown to you. You try to guess z. Whenever your guess x is not correct yet, I give you a hint how good your guess was. I tell you how many bits in the order of \sigma are correct. That is, I tell you the largest integer i such that x_\sigma(1), ..., x_\sigma(i) are correct. How many guesses do you need to find z? If you think about it, you will quickly find a strategy using O(n^2) guesses. Another moment's thought and you have a strategy succeeding with O(n \log n) guesses. But then? Can you do better? Or have a lower bound proof? We'll see...

This is joint work with Carola Winzen. It was presented in a less funny way at EA 2011.


Benjamin Doerr
--email hidden
passcode not visible
logged in users only

Benjamin Doerr, 11/14/2011 20:39
Benjamin Doerr, 11/10/2011 00:08
Benjamin Doerr, 11/10/2011 00:07 -- Created document.