I'm going to admit, I only skimmed the introduction of the paper, but this quote from the article appears very misleading
> They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.
Assuming "random oracle" means what it typically does, that appears to be a pretty poor characterization of what a random oracle does to a problem.
In particular, a (non-random) oracle is a public string O such that both the algorithm and the function one is trying to compute can depend on O. One valid oracle (probably the most famous interesting one) is the halting oracle: the string that at position with index x tells you whether or not the TM with binary encoding <x> ever halts on an empty input. While access to this string would give you an avenue to solving the standard halting problem in finite time (the time taken to do a single lookup), the halting problem relative to this oracle is still uncomputable because you're now additionally tasked with solving the halting problems for machines that also know what O is, and therefore can pull off the same self-simulation trick to fool you as in the standard proof.
An algorithm existing relative to a random oracle means that if each digit of O were sampled from independent fair coin flips, then with probability 1 the algorithm could solve the problem. This is different from the standard definition of randomized complexity classes in that the correct solution to a problem can still directly depend on O itself.
Relative a random oracle, it is an exercise to prove some results of otherwise immense magnitude such as P≠NP, #P≠PSPACE, IP≠PSPACE, and so on. But the problems underlying these separations tend to be contrived, e.g. "does the string O contain a substring from some set A", where A is chosen specifically so that (i) it contains a string in O with an (a priori) 50% chance, (ii) one class information-theoretically cannot identify this string without enumerating beyond its available resource constraints, and (iii) the other class can exploit its added power to easily solve the problem. For example, perhaps a "P algorithm" would need to brute force 2^N positions for such a string, but an "NP algorithm" can nondeterministically guess where in the oracle to look to find it.
Random oracles are great for proving separations, but their applicability to the underlying classes is limited. Concretely, the result I mentioned above of IP≠PSPACE is straight-up wrong in the unrelativized world. The oracle isn't just playing with the randomness involved, it's fundamentally asking which questions one is allowed to ask, and opens an avenue toward posing a whole bunch of "junk" problems that become uninteresting as soon as the pure noise oracle string O is discarded.
In light of this, I'm not sure how to view this result. Is it to be read as Yet Another Random Oracle Separation, or is there something deeper here that I should take away from the result?
> They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.
Assuming "random oracle" means what it typically does, that appears to be a pretty poor characterization of what a random oracle does to a problem.
In particular, a (non-random) oracle is a public string O such that both the algorithm and the function one is trying to compute can depend on O. One valid oracle (probably the most famous interesting one) is the halting oracle: the string that at position with index x tells you whether or not the TM with binary encoding <x> ever halts on an empty input. While access to this string would give you an avenue to solving the standard halting problem in finite time (the time taken to do a single lookup), the halting problem relative to this oracle is still uncomputable because you're now additionally tasked with solving the halting problems for machines that also know what O is, and therefore can pull off the same self-simulation trick to fool you as in the standard proof.
An algorithm existing relative to a random oracle means that if each digit of O were sampled from independent fair coin flips, then with probability 1 the algorithm could solve the problem. This is different from the standard definition of randomized complexity classes in that the correct solution to a problem can still directly depend on O itself.
Relative a random oracle, it is an exercise to prove some results of otherwise immense magnitude such as P≠NP, #P≠PSPACE, IP≠PSPACE, and so on. But the problems underlying these separations tend to be contrived, e.g. "does the string O contain a substring from some set A", where A is chosen specifically so that (i) it contains a string in O with an (a priori) 50% chance, (ii) one class information-theoretically cannot identify this string without enumerating beyond its available resource constraints, and (iii) the other class can exploit its added power to easily solve the problem. For example, perhaps a "P algorithm" would need to brute force 2^N positions for such a string, but an "NP algorithm" can nondeterministically guess where in the oracle to look to find it.
Random oracles are great for proving separations, but their applicability to the underlying classes is limited. Concretely, the result I mentioned above of IP≠PSPACE is straight-up wrong in the unrelativized world. The oracle isn't just playing with the randomness involved, it's fundamentally asking which questions one is allowed to ask, and opens an avenue toward posing a whole bunch of "junk" problems that become uninteresting as soon as the pure noise oracle string O is discarded.
In light of this, I'm not sure how to view this result. Is it to be read as Yet Another Random Oracle Separation, or is there something deeper here that I should take away from the result?