Jin-Yi Cai (University of Wisconsin, Madison):
Random Access to Advice Strings and Collapsing Results
We propose a model of computation where a Turing machine is given random
access to an advice string. With random access, an advice string of
exponential length becomes meaningful for polynomially bounded complexity
classes. We compare the power of complexity classes under this model. It
gives a more stringent notion than the usual model of computation with
relativization. Under this model of random access, we prove that there exist
advice strings such that the Polynomial-time Hierarchy PH and Parity
Polynomial-time $\parityP$ all collapse to P. Our main proof technique uses
the decision tree lower bounds for constant depth
circuits~\cite{yao:focs85,cai:stoc86,hastad:stoc86}, and the algebraic
machinery of Razborov and Smolensky.
Joint work with Osamu Watanabe.