Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-049 | 19th October 1995 00:00

Boolean complexity classes vs. their arithmetic analogs

RSS-Feed




TR95-049
Authors: Anna Gal, Avi Wigderson
Publication: 20th October 1995 08:08
Downloads: 1033
Keywords: 


Abstract:


This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These reductions are based on the
Isolation Lemma of Mulmuley-Vazirani-Vazirani.



ISSN 1433-8092 | Imprint