Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-030 | 25th April 2001 00:00

S_2^p \subseteq ZPP^{NP}

RSS-Feed




TR01-030
Authors: Jin-Yi Cai
Publication: 26th April 2001 14:15
Downloads: 2519
Keywords: 


Abstract:

We show that the class {\rm S}_2^p is a subclass of
{{\rm ZPP}^{\rm NP}}. The proof uses universal hashing, approximate counting
and witness sampling. As a consequence, a collapse first noticed by
Samik Sengupta that the assumption NP has small circuits collapses
PH to {\rm S}_2^p
becomes the strongest version to date of the Karp-Lipton Theorem.



ISSN 1433-8092 | Imprint