2-Local Random Reductions to 3-Valued Functions
2015
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 function, then L 2 PSPACE=poly. Fortnow and Szegedy quantitatively improved Yao's result to show that such languages are in fact in NP=poly (Information Processing Letters, 1992). In this paper we extend Yao's result to show that if a language L is 2-locally-random reducible to a target function which takes values in f0; 1; 2g, then L 2 PSPACE=poly. 1