Stephen A. Cook

132 papers A* 36A 1B 7Journal 73Unranked 6

Year	Rank	Type	Title / Venue / Authors
2023	—	`ch.`	A Survey of Classes of Primitive Recursive Functions. Logic, Automata, and Computational Complexity Stephen A. Cook
2023	—	`ch.`	A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. Logic, Automata, and Computational Complexity Allan Borodin, Stephen A. Cook
2023	—	`ch.`	Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. Logic, Automata, and Computational Complexity Stephen A. Cook
2023	—	`ch.`	Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version). Logic, Automata, and Computational Complexity Stephen A. Cook
2023	—	`ch.`	Pebbles and Branching Programs for Tree Evaluation. Logic, Automata, and Computational Complexity Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2023	—	`ch.`	The 1982 ACM Turing Award Lecture: An Overview of Computational Complexity. Logic, Automata, and Computational Complexity Stephen A. Cook
2023	—	`ch.`	The Complexity of Theorem-Proving Procedures. Logic, Automata, and Computational Complexity Stephen A. Cook
2023	—	`ch.`	The Relative Efficiency of Propositional Proof Systems. Logic, Automata, and Computational Complexity Stephen A. Cook, Robert A. Reckhow
2023	—	`ch.`	Towards a Complexity Theory of Synchronous Parallel Computation. Logic, Automata, and Computational Complexity Stephen A. Cook
2021	J	`jnl`	Uniform, Integral, and Feasible Proofs for the Determinant Identities. J. ACM Iddo Tzameret, Stephen A. Cook
2018	J	`jnl`	Uniform, Integral and Feasible Proofs for the Determinant Identities. CoRR Iddo Tzameret, Stephen A. Cook
2018	J	`jnl`	Uniform, Integral and Feasible Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. Iddo Tzameret, Stephen A. Cook
2017	J	`jnl`	A Survey of Classes of Primitive Recursive Functions. Electron. Colloquium Comput. Complex. Stephen A. Cook, Bruce M. Kapron
2017	A*	`conf`	Uniform, integral and efficient proofs for the determinant identities. LICS Iddo Tzameret, Stephen A. Cook
2016	A*	`conf`	Exponential Lower Bounds for Monotone Span Programs. FOCS Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook
2016	J	`jnl`	Exponential Lower Bounds for Monotone Span Programs. Electron. Colloquium Comput. Complex. Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman
2016	A*	`conf`	Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. ICALP Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi
2016	J	`jnl`	Relativizing small complexity classes and their theories. Comput. Complex. Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
2014	J	`jnl`	The Hardness of Being Private. ACM Trans. Comput. Theory Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
2014	J	`jnl`	The complexity of the comparator circuit value problem. ACM Trans. Comput. Theory Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
2013	A*	`conf`	Average Case Lower Bounds for Monotone Switching Networks. FOCS Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook
2013	J	`jnl`	Average Case Lower Bounds for Monotone Switching Networks. Electron. Colloquium Comput. Complex. Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook
2013	J	`jnl`	Complexity Theory for Operators in Analysis CoRR Akitoshi Kawamura, Stephen A. Cook
2013	B	`conf`	Theories for Subexponential-size Bounded-depth Frege Proofs. CSL Kaveh Ghasemloo, Stephen A. Cook
2012	J	`jnl`	Complexity Theory for Operators in Analysis. ACM Trans. Comput. Theory Akitoshi Kawamura, Stephen A. Cook
2012	B	`conf`	Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk). CSL Stephen A. Cook
2012	J	`jnl`	Formal Theories for Linear Algebra Log. Methods Comput. Sci. Stephen A. Cook, Lila Fontes
2012	J	`jnl`	Pebbles and Branching Programs for Tree Evaluation. ACM Trans. Comput. Theory Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2012	J	`jnl`	Relativized Propositional Calculus CoRR Stephen A. Cook
2012	J	`jnl`	Relativizing Small Complexity Classes and their Theories CoRR Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
2012	J	`jnl`	The Complexity of Proving the Discrete Jordan Curve Theorem. ACM Trans. Comput. Log. Phuong Nguyen, Stephen A. Cook
2012	J	`jnl`	The Complexity of the Comparator Circuit Value Problem CoRR Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
2012	A	`conf`	The Hardness of Being Private. CCC Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
2011	B	`conf`	A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem. CSL Dai Tri Man Le, Stephen A. Cook, Yuli Ye
2011	J	`jnl`	Complexity Classes and Theories for the Comparator Circuit Value Problem CoRR Dai Tri Man Le, Stephen A. Cook, Yuli Ye
2011	J	`jnl`	Formalizing Randomized Matching Algorithms Log. Methods Comput. Sci. Dai Tri Man Le, Stephen A. Cook
2011	A*	`conf`	Formalizing Randomized Matching Algorithms. LICS Dai Tri Man Le, Stephen A. Cook
2010	A*	`conf`	Complexity theory for operators in analysis. STOC Akitoshi Kawamura, Stephen A. Cook
2010	B	`conf`	Formal Theories for Linear Algebra. CSL Stephen A. Cook, Lila Fontes
2010	J	`jnl`	Pebbles and Branching Programs for Tree Evaluation CoRR Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2010	J	`jnl`	The Complexity of Proving the Discrete Jordan Curve Theorem CoRR Phuong Nguyen, Stephen A. Cook
2009	B	`conf`	Branching Programs for Tree Evaluation. MFCS Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009	—	`conf`	Fractional Pebbling and Thrifty Branching Programs. FSTTCS Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2007	J	`jnl`	Consequences of the provability of J. Symb. Log. Stephen A. Cook, Jan Krajícek
2007	B	`conf`	Relativizing Small Complexity Classes and Their Theories. CSL Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
2007	A*	`conf`	The Complexity of Proving the Discrete Jordan Curve Theorem. LICS Phuong Nguyen, Stephen A. Cook
2006	J	`jnl`	Comments on Beckmann's Uniform Reducts CoRR Stephen A. Cook
2006	J	`jnl`	The strength of replacement in weak arithmetic. ACM Trans. Comput. Log. Stephen A. Cook, Neil Thapen
2006	J	`jnl`	Theories for TC0 and Other Small Complexity Classes. Log. Methods Comput. Sci. Phuong Nguyen, Stephen A. Cook
2005	J	`jnl`	Computing over the Reals: Foundations for Scientific Computing CoRR Mark Braverman, Stephen A. Cook
2005	J	`jnl`	Quantified propositional calculus and a second-order theory for NC Arch. Math. Log. Stephen A. Cook, Tsuyoshi Morioka
2005	J	`jnl`	Theories for TC0 and Other Small Complexity Classes CoRR Phuong Nguyen, Stephen A. Cook
2004	A*	`conf`	A Second-Order Theory for NL. LICS Stephen A. Cook, Antonina Kolokolova
2004	A*	`conf`	The Strength of Replacement in Weak Arithmetic. LICS Stephen A. Cook, Neil Thapen
2004	J	`jnl`	The proof complexity of linear algebra. Ann. Pure Appl. Log. Michael Soltys, Stephen A. Cook
2004	J	`jnl`	The strength of replacement in weak arithmetic CoRR Stephen A. Cook, Neil Thapen
2004	A*	`conf`	VTC LICS Phuong Nguyen, Stephen A. Cook
2003	J	`jnl`	A Complete Axiomatization for Blocks World. J. Log. Comput. Stephen A. Cook, Yongmei Liu
2003	J	`jnl`	A second-order system for polytime reasoning based on Grädel's theorem. Ann. Pure Appl. Log. Stephen A. Cook, Antonina Kolokolova
2003	J	`jnl`	The importance of the P versus NP question. J. ACM Stephen A. Cook
2002	—	`conf`	A Complete Axiomatization for Blocks World. AI&M Stephen A. Cook, Yongmei Liu
2002	A*	`conf`	Complexity Classes, Propositional Proof Systems, and Formal Theories. LICS Stephen A. Cook
2002	A*	`conf`	The Proof Complexity of Linear Algebra. LICS Michael Soltys, Stephen A. Cook
2002	J	`jnl`	The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy. Distributed Comput. Stephen A. Cook, Jan K. Pachl, Irwin S. Pressman
2001	A*	`conf`	A Second-Order System for Polytime Reasoning Using Graedel's Theorem. LICS Stephen A. Cook, Antonina Kolokolova
2001	J	`jnl`	A second-order system for polynomial-time reasoning based on Graedel's theorem Electron. Colloquium Comput. Complex. Stephen A. Cook, Antonina Kolokolova
2000	J	`jnl`	Efficiently Approximable Real-Valued Functions Electron. Colloquium Comput. Complex. Valentine Kabanets, Charles Rackoff, Stephen A. Cook
1999	J	`jnl`	An Exponential Lower Bound for the Size of Monotone Real Circuits. J. Comput. Syst. Sci. Armin Haken, Stephen A. Cook
1998	J	`jnl`	The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1997	J	`jnl`	A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. Inf. Comput. Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami
1996	J	`jnl`	A New Characterization of Type-2 Feasibility. SIAM J. Comput. Bruce M. Kapron, Stephen A. Cook
1996	—	`conf`	Finding hard instances of the satisfiability problem: A survey. Satisfiability Problem: Theory and Applications Stephen A. Cook, David G. Mitchell
1995	A*	`conf`	The relative complexity of NP search problems. STOC Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1993	J	`jnl`	Functional Interpretations of Feasibly Constructive Arithmetic. Ann. Pure Appl. Log. Stephen A. Cook, Alasdair Urquhart
1993	J	`jnl`	Parallel Pointer Machines. Comput. Complex. Stephen A. Cook, Patrick W. Dymond
1992	A*	`conf`	A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract) STOC Stephen J. Bellantoni, Stephen A. Cook
1992	J	`jnl`	A New Recursion-Theoretic Characterization of the Polytime Functions. Comput. Complex. Stephen J. Bellantoni, Stephen A. Cook
1992	J	`jnl`	An Optimal Parallel Algorithm for Formula Evaluation. SIAM J. Comput. Samuel R. Buss, Stephen A. Cook, A. Gupta, V. Ramachandran
1992	—	`conf`	The optimal placement of replicas in a network using a read any - write all policy. CASCON Irwin S. Pressman, Stephen A. Cook, Jan K. Pachl
1991	A*	`conf`	A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) FOCS Bruce M. Kapron, Stephen A. Cook
1990	J	`jnl`	A Feasibly Constructive Lower Bound for Resolution Proofs. Inf. Process. Lett. Stephen A. Cook, Toniann Pitassi
1989	A*	`conf`	Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract) FOCS Stephen A. Cook, Bruce M. Kapron
1989	J	`jnl`	Complexity Theory of Parallel Time and Hardware Inf. Comput. Patrick W. Dymond, Stephen A. Cook
1989	J	`jnl`	Erratum: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1989	A*	`conf`	Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) STOC Stephen A. Cook, Alasdair Urquhart
1989	J	`jnl`	Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1988	J	`jnl`	A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula. Inf. Process. Lett. Stephen A. Cook, Michael Luby
1988	J	`jnl`	Short Propositional Formulas Represent Nondeterministic Computations. Inf. Process. Lett. Stephen A. Cook
1988	—	`conf`	Two applications of complementation via inductive counting. SCT Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1987	J	`jnl`	Problems Complete for Deterministic Logarithmic Space. J. Algorithms Stephen A. Cook, Pierre McKenzie
1987	J	`jnl`	The Parallel Complexity of Abelian Permutation Group Problems. SIAM J. Comput. Pierre McKenzie, Stephen A. Cook
1986	J	`jnl`	Log Depth Circuits for Division and Related Problems. SIAM J. Comput. Paul Beame, Stephen A. Cook, H. James Hoover
1986	J	`jnl`	Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM J. Comput. Stephen A. Cook, Cynthia Dwork, Rüdiger Reischuk
1985	J	`jnl`	A Depth-Universal Circuit. SIAM J. Comput. Stephen A. Cook, H. James Hoover
1985	J	`jnl`	A Taxonomy of Problems with Fast Parallel Algorithms Inf. Control. Stephen A. Cook
1984	A*	`conf`	Log Depth Circuits for Division and Related Problems FOCS Paul Beame, Stephen A. Cook, H. James Hoover
1983	J	`jnl`	An Overview of Computational Complexity. Commun. ACM Stephen A. Cook
1983	J	`jnl`	Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines Inf. Control. Allan Borodin, Stephen A. Cook, Nicholas Pippenger
1983	B	`conf`	The Classifikation of Problems which have Fast Parallel Algorithms. FCT Stephen A. Cook
1983	A*	`conf`	The Parallel Complexity of the Abelian Permutation Group Membership Problem FOCS Pierre McKenzie, Stephen A. Cook
1983	J	`jnl`	The Recognition of Deterministic CFL's in Small Time and Space Inf. Control. Burchard von Braunmühl, Stephen A. Cook, Kurt Mehlhorn, Rutger Verbeek
1982	J	`jnl`	A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM J. Comput. Allan Borodin, Stephen A. Cook
1982	A*	`conf`	Bounds on the Time for Parallel RAM's to Compute Simple Functions STOC Stephen A. Cook, Cynthia Dwork
1981	J	`jnl`	Corrigendum: Soundness and Completeness of an Axiom System for Program Verification. SIAM J. Comput. Stephen A. Cook
1980	A*	`conf`	A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation STOC Allan Borodin, Stephen A. Cook
1980	A*	`conf`	Hardware Complexity and Parallel Computation (Preliminary Version) FOCS Patrick W. Dymond, Stephen A. Cook
1980	J	`jnl`	Space Lower Bounds for Maze Threadability on Restricted Machines. SIAM J. Comput. Stephen A. Cook, Charles Rackoff
1979	A*	`conf`	Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space STOC Stephen A. Cook
1979	J	`jnl`	The Relative Efficiency of Propositional Proof Systems. J. Symb. Log. Stephen A. Cook, Robert A. Reckhow
1978	J	`jnl`	Soundness and Completeness of an Axiom System for Program Verification. SIAM J. Comput. Stephen A. Cook
1976	J	`jnl`	A short proof of the pigeon hole principle using extended resolution. SIGACT News Stephen A. Cook
1976	J	`jnl`	On the Number of Additions to Compute Specific Polynomials. SIAM J. Comput. Allan Borodin, Stephen A. Cook
1976	J	`jnl`	Storage Requirements for Deterministic Polynomial Time Recognizable Languages. J. Comput. Syst. Sci. Stephen A. Cook, Ravi Sethi
1975	A*	`conf`	An Assertion Language for Data Structures. POPL Stephen A. Cook, Derek C. Oppen
1975	A*	`conf`	Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version) STOC Stephen A. Cook
1975	A*	`conf`	Proving Assertions about Programs that Manipulate Data Structures STOC Derek C. Oppen, Stephen A. Cook
1974	J	`jnl`	An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. Stephen A. Cook
1974	J	`jnl`	Corrections for "On the lengths of proofs in the propositional calculus preliminary version". SIGACT News Stephen A. Cook, Robert A. Reckhow
1974	A*	`conf`	On the Lengths of Proofs in the Propositional Calculus (Preliminary Version) STOC Stephen A. Cook, Robert A. Reckhow
1974	A*	`conf`	On the Number of Additions to Compute Specific Polynomials (Preliminary Version) STOC Allan Borodin, Stephen A. Cook
1974	A*	`conf`	Storage Requirements for Deterministic Polynomial Time Recognizable Languages STOC Stephen A. Cook, Ravi Sethi
1973	J	`jnl`	A Hierarchy for Nondeterministic Time Complexity. J. Comput. Syst. Sci. Stephen A. Cook
1973	A*	`conf`	An Observation on Time-Storage Trade Off STOC Stephen A. Cook
1973	J	`jnl`	Time Bounded Random Access Machines. J. Comput. Syst. Sci. Stephen A. Cook, Robert A. Reckhow
1972	A*	`conf`	A Hierarchy for Nondeterministic Time Complexity STOC Stephen A. Cook
1972	A*	`conf`	Time-Bounded Random Access Machines STOC Stephen A. Cook, Robert A. Reckhow
1971	J	`jnl`	Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. J. ACM Stephen A. Cook
1971	—	`conf`	Linear Time Simulation of Deterministic Two-Way Pushdown Automata. IFIP Congress (1) Stephen A. Cook
1971	A*	`conf`	The Complexity of Theorem-Proving Procedures STOC Stephen A. Cook
1970	A*	`conf`	Path Systems and Language Recognition STOC Stephen A. Cook
1969	A*	`conf`	Variations on Pushdown Machines (Detailed Abstract) STOC Stephen A. Cook
1966	J	`jnl`	The Solvability of the Derivability Problem for One-Normal Systems. J. ACM Stephen A. Cook