Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-062 | 17th June 2005 00:00

2-Local Random Reductions to 3-Valued Functions

RSS-Feed




TR05-062
Authors: A. Pavan, Vinodchandran Variyam
Publication: 22nd June 2005 23:54
Downloads: 960
Keywords: 


Abstract:

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, 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 {0,1,2}, then L is in PSPACE/poly.



ISSN 1433-8092 | Imprint