2 papers
cs.CC2003
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
Russell Impagliazzo, Nathan Segerlind
We show that constant-depth Frege systems with counting axioms modulo polynomially simulate Nullstellensatz refutations modulo . Central to this is a new definition of reduc…
quant-ph1996
Limitations of Noisy Reversible Computation
D. Aharonov, M. Ben-Or, R. Impagliazzo +1
Noisy computation and reversible computation have been studied separately, and it is known that they are as powerful as unrestricted computation. We study the case where both noise…