Yao (in a lecture at DIMACS Workshop on structural complexity and
cryptography) showed that if a language L is 2-locally-random
reducible to a Boolean functio, then L is in PSPACE/poly.
Fortnow and Szegedy quantitatively improved Yao's result to show that
such languages are in fact in NP/poly (Information Processing Letters, ... more >>>