All Questions Answered

Suppose you think of a number between 1 and a million, and I have to guess it. I can only ask one type of question: “Is the number less than X?”. What is the best strategy you could use? This sounds a bit funny. Isn’t it the person doing the guessing and not the person who picked the number who needs a strategy?

If you are actually playing this game though, there is no reason for you to commit to a number until you are forced to. Instead, you just need to make sure you don’t contradict yourself in response to my questions!

So, if my first question is “Is the number less than 1000?”, you should certainly say no! Answering no leaves far more uncertainty in the game.

In this game, your optimal strategy is just to always answer so as to leave the larger amount of uncertainty. If you do this, you can always force me to ask about 20 questions (i.e., ${\log }_{2}1000000\approx 19.9$). You are behaving in an adversarial manner.

Computers spend a decent amount of time putting things in order: sorting. In comparison algorithms, for two of the things, computers do this just by asking “Is ?”, for lots of $A$ and $B$. If a computer is sorting $n$ numbers, there is a folk-lore result that an efficient adversary can force it to ask about $\frac{1}{2}n{\log }_{2}n$ questions. By “efficient” here, we really mean it: the adversary uses no randomness, and operates in polynomial time per comparison (in fact, it operates in constant time!).

So the question is, is there an efficient adversary (that doesn’t use randomness), that forces more than $\frac{1}{2}n{\log }_{2}n$ questions? There is! In 2019, an adversary forcing about $0.578n{\log }_{2}n$ questions was first discovered. And so a natural question is, how close to $1$ as the leading constant can an adversary get?

Over the years, I have cooked up various adversaries to see if I could do better. I couldn’t.

I have asked various AI models over the years, how close to $1$ they can get. They all failed to get there too. Even GPT6 Astra Pro failed!

Then, one day I had an expiring ChatGPT Astra reset. I set Codex on Ultra mode to work with the goal (and a small restriction: to focus on “discrete and graph-like constructions” – yes, this is my contribution, LOL). 27 hours later:

Although I’ve been interested in computer science since I was a child, I always (or often enough, at least!) had to admit to myself that I was really a spectator. During my PhD days, I was happy to try out some research. It was always obvious to me though that the frontier was beyond me. Despite that, I still found many of the most satisfying experiences of my life doing research. I can remember particular hours of my life very vividly as I slowly, slowly understood something. Interestingly, these occasions were mostly without a pen and paper or a computer.

Still though, I did not delude myself into thinking my contributions really mattered to the subject (they certainly mattered to me, though!). I knew other humans could probably do months of my work in days or even hours.

The new adversary that Astra discovered is actually pleasingly simple. The analysis isn’t easy, but its gist isn’t too hard either. Yet the adversary is also a big-Oh bomb. The leading constants are absolutely hilarious. Now though, I’m emboldened to ask more questions:

Is there a deterministic sorting adversary, using only $O(\mathrm{polylog}n)$ time per comparison, that forces any sorting algorithm to perform $(1-o(1))n{\log }_{2}n$ comparisons?

(I think probably not?)