63 citations · 171 across the 13 of their papers we have counts for
14 papers
Uniform, Integral and Feasible Proofs for the Determinant Identities
Iddo Tzameret, Stephen A. Cook
Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for…
Complexity Theory for Operators in Analysis
Akitoshi Kawamura, Stephen Cook
We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that…
The Complexity of the Comparator Circuit Value Problem
Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL \subseteq C…
Relativizing Small Complexity Classes and their Theories
Klaus Aehlig, Stephen Cook, Phuong Nguyen
Existing definitions of the relativizations of \NCOne, Ł and \NL\ do not preserve the inclusions $\NCOne \subseteq Ł$, $\NL\subseteq \ACOne$. We start by giving the first definitio…
Relativized Propositional Calculus
Stephen Cook
Proof systems for the Relativized Propositional Calculus are defined and compared.
Complexity Classes and Theories for the Comparator Circuit Value Problem
Stephen A. Cook, Dai Tri Man Le, Yuli Ye
Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem. He proved that several other problems are complete f…