We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

Circuits composed of threshold gates (McCulloch-Pitts neurons, or
perceptrons) are simplified models of neural circuits with the
advantage that they are theoretically more tractable than their
biological counterparts. However, when such threshold circuits are
designed to perform a specific computational task they usually
differ ... more >>>