AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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