Title :
Errata for circuit size relative to pseudorandom oracles
Author :
Lutz, Jack H. ; Schmidt, William J.
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
fDate :
30 Jun-3 Jul 1991
Abstract :
In the above-titled paper (see Proc. Fifth Structure in Complexity Theory Conf., 1990, p.268-86) by the present authors it was claimed that two specified separations hold relative to every pspace-random oracle A, and relative to almost every oracle A∈ESPACE. It is noted that the proofs given were not correct and that corrected proofs are being published elsewhere. Some further discussion regarding these proofs is presented
Keywords :
computational complexity; circuit size; pseudorandom oracles; Circuits; Complexity theory; Computer science; Information science; Lifting equipment; Writing;
Conference_Titel :
Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-2255-5
DOI :
10.1109/SCT.1991.160284
