Boolean complexity classes vs. their arithmetic analogs
Anna G�l, Avi Wigderson · Random Structures and Algorithms · 1996
This paper provides logspace and small circuit depth analogs of the result of Valiant and Vazirani, which is a randomized (or nonuniform) reduction from NP to its arithmetic analog ⊕ P. We show a similar randomized reduction between the Boolean classes NL and semiunbounded fan-in Boolean circuits and their arithmetic counterparts. These reductions are based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. Combinatorially our results can be viewed as simple (logspace) transformations of existential quantifiers into counting quantifiers in graphs and shallow circuits. © 1996 John Wiley & Sons, Inc.