In contrast to deterministic or nondeterministic computation, it is a fundamental open problem in randomized computation how to separate different randomized time classes (at this point we do not even know how to separate linear randomized time from ${\mathcal O}(n^{\log n})$ randomized time) or how to compare them relative to ... more >>>

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

Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability proportional to their distance from the code. Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is less immediate ... more >>>

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>