Time isn’t a resource I have a lot left to spend, but it seems really worth it to try and understand this fully (it’s not everyday I come across something as puzzling which also has been solved). I’ll do my homework without bugging you more about it. ]]>

Haha, I’m trying!

I’m even struggling with the concept of “random algorithm”, e.g when you write:

“[…] the minimum number of queries made by any randomized algorithm that computes f(X) with success probability at least 2/3 for every X”

How do you come up with this probability?

Do you mean that over the entire set of possible input (finite set of 2^n inputs for n), the fraction of inputs for which it works is exactly > 2/3?

Or do you mean that if we were to feed that same one input to the algorithm, over and over, the algorithm could give a true or false answer, but it would come up with the right answer 2/3 of the time (asymptotic value as we feed it the same input an infinite number of times)? And that would be true for any one input (of a possible 2^n) we decide to feed it.

]]>https://fedyapetrov.wordpress.com/2019/07/03/low-level-variant-of-huangs-argument-for-sensitivity-conjecture/ ]]>

“you may need to make choices that break complete permutation symmetry among the bits”

I figured that if the 2^N entries are laid down in increasing order (0, 1, 2, 3,… 2^N), looking at the bits, and the parity, there’s a kind of recursive symmetry to it – no matter what subset of bits you consider, half of them are gonna be parity 1, the other parity 0.

But I still don’t see how scrambling that symmetry would make it so that you magically get more lucky on average.

What puzzles me is that if you consider sampling N-1 bits instead of √n (so you know all the bits except one), you’re still left having to “beat” a random coin flip. Seems odd that looking at less bits would give you an edge…

Brem #66

“Running through simple cases by hand, with two bits guessed out of 3 the best strategy is on 00 guess 1, on 01, flip a coin, and on 11 guess 0. That gets 2/3 reliability in 6/8 of the cases and zero in the others.”

I don’t see it… 00, guess 1, you’re right half the time, 11, guess 0, you’re right half the time, and 01, flip a coin, you’re still right half the time.

]]>