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