Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOGSPACE COMPUTATIONS:
Reports tagged with Logspace computations:
TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

Boolean complexity classes vs. their arithmetic analogs


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 ... more >>>




ISSN 1433-8092 | Imprint