From Scott Aaronson's blog post on the paper:<p>> Basically, they need to show that, for every k, there are problems that can be solved by small circuits with k layers of AND, OR, and NOT gates, but for which the answer can’t even be guessed, noticeably better than chance, by any small circuit with only k-1 layers of AND, OR, and NOT gates.
I'm struggling to understand the concept of a "random oracle". I assume any oracle is just an infinite string of bits, or natural numbers, or suchnot, and thus is countably infinite (and has order omega), so there would be uncountably many (2^aleph-null) such oracles - how does one pick one at random, such that they are (I assume) equally likely? How does one pick a random element from an uncountable set?<p>And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?