Stephen A. Cook

List of publications from the DBLP Bibliography Server - FAQ
Other views: by type - by year (modern) - classic-C

Ask others: ACM DL/Guide -

- CSB - MetaPress - Google - Bing - Yahoo

	2013
i12		Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook: Average Case Lower Bounds for Monotone Switching Networks. Electronic Colloquium on Computational Complexity (ECCC) 20: 54 (2013)
	2012
j48		Stephen A. Cook, Lila Fontes: Formal Theories for Linear Algebra. Logical Methods in Computer Science 8(1) (2012)
j47		Phuong Nguyen, Stephen A. Cook: The Complexity of Proving the Discrete Jordan Curve Theorem. ACM Trans. Comput. Log. 13(1): 9 (2012)
j46		Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam: Pebbles and Branching Programs for Tree Evaluation. TOCT 3(2): 4 (2012)
j45		Akitoshi Kawamura, Stephen A. Cook: Complexity Theory for Operators in Analysis. TOCT 4(2): 5 (2012)
c45		Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi: The Hardness of Being Private. IEEE Conference on Computational Complexity 2012: 192-202
c44		Stephen A. Cook: Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk). CSL 2012: 9-11
i11		Klaus Aehlig, Stephen A. Cook, Phuong Nguyen: Relativizing Small Complexity Classes and their Theories. CoRR abs/1204.5508 (2012)
i10		Stephen A. Cook, Yuval Filmus, Dai Tri Man Le: The Complexity of the Comparator Circuit Value Problem. CoRR abs/1208.2721 (2012)
	2011
j44		Dai Tri Man Le, Stephen A. Cook: Formalizing Randomized Matching Algorithms. Logical Methods in Computer Science 8(3) (2011)
c43		Dai Tri Man Le, Stephen A. Cook, Yuli Ye: A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem. CSL 2011: 381-395
c42		Dai Tri Man Le, Stephen A. Cook: Formalizing Randomized Matching Algorithms. LICS 2011: 185-194
i9		Dai Tri Man Le, Stephen A. Cook, Yuli Ye: Complexity Classes and Theories for the Comparator Circuit Value Problem. CoRR abs/1106.4142 (2011)
	2010
c41		Stephen A. Cook, Lila Fontes: Formal Theories for Linear Algebra. CSL 2010: 245-259
c40		Akitoshi Kawamura, Stephen A. Cook: Complexity theory for operators in analysis. STOC 2010: 495-502
i8		Phuong Nguyen, Stephen A. Cook: The Complexity of Proving the Discrete Jordan Curve Theorem. CoRR abs/1002.2954 (2010)
i7		Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam: Pebbles and Branching Programs for Tree Evaluation. CoRR abs/1005.2642 (2010)
	2009
c39		Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Fractional Pebbling and Thrifty Branching Programs. FSTTCS 2009: 109-120
c38		Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
	2007
j43		Stephen A. Cook, Jan Krajícek: Consequences of the provability of NP SUBSET OF OR EQUAL TO P/poly. J. Symb. Log. 72(4): 1353-1371 (2007)
c37		Klaus Aehlig, Stephen A. Cook, Phuong Nguyen: Relativizing Small Complexity Classes and Their Theories. CSL 2007: 374-388
c36		Phuong Nguyen, Stephen A. Cook: The Complexity of Proving the Discrete Jordan Curve Theorem. LICS 2007: 245-256
	2006
j42		Phuong Nguyen, Stephen A. Cook: Theories for TC0 and Other Small Complexity Classes. Logical Methods in Computer Science 2(1) (2006)
j41		Stephen A. Cook, Neil Thapen: The strength of replacement in weak arithmetic. ACM Trans. Comput. Log. 7(4): 749-764 (2006)
i6		Stephen A. Cook: Comments on Beckmann's Uniform Reducts. CoRR abs/cs/0601086 (2006)
	2005
j40		Stephen A. Cook, Tsuyoshi Morioka: Quantified propositional calculus and a second-order theory for NC¹. Arch. Math. Log. 44(6): 711-749 (2005)
i5		Phuong Nguyen, Stephen A. Cook: Theories for TC0 and Other Small Complexity Classes. CoRR abs/cs/0505013 (2005)
i4		Mark Braverman, Stephen A. Cook: Computing over the Reals: Foundations for Scientific Computing. CoRR abs/cs/0509042 (2005)
	2004
j39		Michael Soltys, Stephen A. Cook: The proof complexity of linear algebra. Ann. Pure Appl. Logic 130(1-3): 277-323 (2004)
c35		Stephen A. Cook, Neil Thapen: The Strength of Replacement in Weak Arithmetic. LICS 2004: 256-264
c34		Phuong Nguyen, Stephen A. Cook: VTC ^circ: A Second-Order Theory for TC^circ. LICS 2004: 378-387
c33		Stephen A. Cook, Antonina Kolokolova: A Second-Order Theory for NL. LICS 2004: 398-407
i3		Stephen A. Cook, Neil Thapen: The strength of replacement in weak arithmetic. CoRR cs.LO/0409015 (2004)
	2003
j38		Stephen A. Cook, Antonina Kolokolova: A second-order system for polytime reasoning based on Grädel's theorem. Ann. Pure Appl. Logic 124(1-3): 193-231 (2003)
j37		Stephen A. Cook: The importance of the P versus NP question. J. ACM 50(1): 27-29 (2003)
j36		Stephen A. Cook, Yongmei Liu: A Complete Axiomatization for Blocks World. J. Log. Comput. 13(4): 581-594 (2003)
	2002
j35		Stephen A. Cook, Jan K. Pachl, Irwin S. Pressman: The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy. Distributed Computing 15(1): 57-66 (2002)
c32		Stephen A. Cook, Yongmei Liu: A Complete Axiomatization for Blocks World. AMAI 2002
c31		Stephen A. Cook, Yongmei Liu: A Complete Axiomatization for Blocks World. ISAIM 2002
c30		Stephen A. Cook: Complexity Classes, Propositional Proof Systems, and Formal Theories. LICS 2002: 311
c29		Michael Soltys, Stephen A. Cook: The Proof Complexity of Linear Algebra. LICS 2002: 335-344
	2001
c28		Stephen A. Cook, Antonina Kolokolova: A Second-Order System for Polytime Reasoning Using Graedel's Theorem. LICS 2001: 177-186
i2		Stephen A. Cook, Antonina Kolokolova: A second-order system for polynomial-time reasoning based on Graedel's theorem. Electronic Colloquium on Computational Complexity (ECCC) 8(24) (2001)
	2000
i1		Valentine Kabanets, Charles Rackoff, Stephen A. Cook: Efficiently Approximable Real-Valued Functions. Electronic Colloquium on Computational Complexity (ECCC) 7(34) (2000)
	1999
j34		Armin Haken, Stephen A. Cook: An Exponential Lower Bound for the Size of Monotone Real Circuits. J. Comput. Syst. Sci. 58(2): 326-335 (1999)
	1998
j33		Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. 57(1): 3-19 (1998)
	1997
j32		Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami: A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. Inf. Comput. 137(2): 159-170 (1997)
	1996
j31		Bruce M. Kapron, Stephen A. Cook: A New Characterization of Type-2 Feasibility. SIAM J. Comput. 25(1): 117-132 (1996)
	1995
c27		Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The relative complexity of NP search problems. STOC 1995: 303-314
	1993
j30		Stephen A. Cook, Alasdair Urquhart: Functional Interpretations of Feasibly Constructive Arithmetic. Ann. Pure Appl. Logic 63(2): 103-200 (1993)
j29		Stephen A. Cook, Patrick W. Dymond: Parallel Pointer Machines. Computational Complexity 3: 19-30 (1993)
	1992
j28		Stephen Bellantoni, Stephen A. Cook: A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2: 97-110 (1992)
c26		Irwin S. Pressman, Stephen A. Cook, Jan K. Pachl: The optimal placement of replicas in a network using a read any - write all policy. CASCON 1992: 189-201
c25		Stephen Bellantoni, Stephen A. Cook: A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract). STOC 1992: 283-293
	1991
c24		Bruce M. Kapron, Stephen A. Cook: A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract). FOCS 1991: 342-347
	1990
j27		Stephen A. Cook, Toniann Pitassi: A Feasibly Constructive Lower Bound for Resolution Proofs. Inf. Process. Lett. 34(2): 81-85 (1990)
	1989
j26		Patrick W. Dymond, Stephen A. Cook: Complexity Theory of Parallel Time and Hardware. Inf. Comput. 80(3): 205-226 (1989)
j25		Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(3): 559-578 (1989)
j24		Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa: Erratum: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(6): 1283 (1989)
c23		Stephen A. Cook, Bruce M. Kapron: Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract). FOCS 1989: 154-159
c22		Stephen A. Cook, Alasdair Urquhart: Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract). STOC 1989: 107-112
	1988
j23		Stephen A. Cook: Short Propositional Formulas Represent Nondeterministic Computations. Inf. Process. Lett. 26(5): 269-270 (1988)
j22		Stephen A. Cook, Michael Luby: A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula. Inf. Process. Lett. 27(3): 141-145 (1988)
c21		Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa: Two applications of complementation via inductive counting. Structure in Complexity Theory Conference 1988: 116-125
	1987
j21		Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987)
j20		Pierre McKenzie, Stephen A. Cook: The Parallel Complexity of Abelian Permutation Group Problems. SIAM J. Comput. 16(5): 880-909 (1987)
	1986
j19		Stephen A. Cook, Cynthia Dwork, Rüdiger Reischuk: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM J. Comput. 15(1): 87-97 (1986)
j18		Paul Beame, Stephen A. Cook, H. James Hoover: Log Depth Circuits for Division and Related Problems. SIAM J. Comput. 15(4): 994-1003 (1986)
	1985
j17		Stephen A. Cook: A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1-3): 2-21 (1985)
j16		Stephen A. Cook, H. James Hoover: A Depth-Universal Circuit. SIAM J. Comput. 14(4): 833-839 (1985)
	1984
c20		Paul Beame, Stephen A. Cook, H. James Hoover: Log Depth Circuits for Division and Related Problems. FOCS 1984: 1-6
	1983
j15		Stephen A. Cook: An Overview of Computational Complexity. Commun. ACM 26(6): 400-408 (1983)
j14		Burchard von Braunmühl, Stephen A. Cook, Kurt Mehlhorn, Rutger Verbeek: The Recognition of Deterministic CFL's in Small Time and Space. Information and Control 56(1/2): 34-51 (1983)
j13		Allan Borodin, Stephen A. Cook, Nicholas Pippenger: Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines. Information and Control 58(1-3): 113-136 (1983)
c19		Stephen A. Cook: The Classifikation of Problems which have Fast Parallel Algorithms. FCT 1983: 78-93
c18		Pierre McKenzie, Stephen A. Cook: The Parallel Complexity of the Abelian Permutation Group Membership Problem. FOCS 1983: 154-161
	1982
j12		Allan Borodin, Stephen A. Cook: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM J. Comput. 11(2): 287-297 (1982)
c17		Stephen A. Cook, Cynthia Dwork: Bounds on the Time for Parallel RAM's to Compute Simple Functions. STOC 1982: 231-233
	1981
j11		Stephen A. Cook: Corrigendum: Soundness and Completeness of an Axiom System for Program Verification. SIAM J. Comput. 10(3): 612 (1981)
	1980
j10		Stephen A. Cook, Charles Rackoff: Space Lower Bounds for Maze Threadability on Restricted Machines. SIAM J. Comput. 9(3): 636-652 (1980)
c16		Patrick W. Dymond, Stephen A. Cook: Hardware Complexity and Parallel Computation (Preliminary Version). FOCS 1980: 360-372
c15		Allan Borodin, Stephen A. Cook: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. STOC 1980: 294-301
	1979
j9		Stephen A. Cook, Robert A. Reckhow: The Relative Efficiency of Propositional Proof Systems. J. Symb. Log. 44(1): 36-50 (1979)
c14		Stephen A. Cook: Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space. STOC 1979: 338-345
	1978
j8		Stephen A. Cook: Soundness and Completeness of an Axiom System for Program Verification. SIAM J. Comput. 7(1): 70-90 (1978)
	1976
j7		Stephen A. Cook, Ravi Sethi: Storage Requirements for Deterministic Polynomial Time Recognizable Languages. J. Comput. Syst. Sci. 13(1): 25-37 (1976)
j6		Allan Borodin, Stephen A. Cook: On the Number of Additions to Compute Specific Polynomials. SIAM J. Comput. 5(1): 146-157 (1976)
	1975
c13		Stephen A. Cook, Derek C. Oppen: An Assertion Language for Data Structures. POPL 1975: 160-166
c12		Stephen A. Cook: Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version). STOC 1975: 83-97
c11		Derek C. Oppen, Stephen A. Cook: Proving Assertions about Programs that Manipulate Data Structures. STOC 1975: 107-116
	1974
j5		Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316 (1974)
c10		Stephen A. Cook, Ravi Sethi: Storage Requirements for Deterministic Polynomial Time Recognizable Languages. STOC 1974: 33-39
c9		Stephen A. Cook, Robert A. Reckhow: On the Lengths of Proofs in the Propositional Calculus (Preliminary Version). STOC 1974: 135-148
c8		Allan Borodin, Stephen A. Cook: On the Number of Additions to Compute Specific Polynomials (Preliminary Version). STOC 1974: 342-347
	1973
j4		Stephen A. Cook: A Hierarchy for Nondeterministic Time Complexity. J. Comput. Syst. Sci. 7(4): 343-353 (1973)
j3		Stephen A. Cook, Robert A. Reckhow: Time Bounded Random Access Machines. J. Comput. Syst. Sci. 7(4): 354-375 (1973)
c7		Stephen A. Cook: An Observation on Time-Storage Trade Off. STOC 1973: 29-33
	1972
c6		Stephen A. Cook, Robert A. Reckhow: Time-Bounded Random Access Machines. STOC 1972: 73-80
c5		Stephen A. Cook: A Hierarchy for Nondeterministic Time Complexity. STOC 1972: 187-192
	1971
j2		Stephen A. Cook: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. J. ACM 18(1): 4-18 (1971)
c4		Stephen A. Cook: Linear Time Simulation of Deterministic Two-Way Pushdown Automata. IFIP Congress (1) 1971: 75-80
c3		Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158
	1970
c2		Stephen A. Cook: Path Systems and Language Recognition. STOC 1970: 70-72
	1969
c1		Stephen A. Cook: Variations on Pushdown Machines (Detailed Abstract). STOC 1969: 229-231
	1966
j1		Stephen A. Cook: The Solvability of the Derivability Problem for One-Normal Systems. J. ACM 13(2): 223-225 (1966)

Coauthor Index

1	Anil Ada	[c45]
2	Klaus Aehlig	[i11] [c37]
3	Paul Beame	[j33] [c27] [j18] [c20]
4	Stephen Bellantoni	[j28] [c25]
5	Allan Borodin	[j25] [j24] [c21] [j13] [j12] [c15] [j6] [c8]
6	Burchard von Braunmühl	[j14]
7	Mark Braverman	[j46] [i7] [c39] [c38] [i4]
8	Arkadev Chattopadhyay	[c45]
9	Cynthia Dwork	[j19] [c17]
10	Patrick W. Dymond	[j29] [j26] [j25] [j24] [c21] [c16]
11	Jeff Edmonds	[j33] [c27]
12	Yuval Filmus	[i12] [i10]
13	Lila Fontes	[j48] [c45] [c41]
14	Armin Haken	[j34]
15	H. James Hoover	[j18] [j16] [c20]
16	Russell Impagliazzo	[j33] [j32] [c27]
17	Valentine Kabanets	[i1]
18	Bruce M. Kapron	[j31] [c24] [c23]
19	Akitoshi Kawamura	[j45] [c40]
20	Antonina Kolokolova	[c33] [j38] [c28] [i2]
21	Michal Koucký	[c45]
22	Jan Krajícek	[j43]
23	Dai Tri Man Le	[i10] [j44] [c43] [c42] [i9]
24	Yongmei Liu	[j36] [c32] [c31]
25	Michael Luby	[j22]
26	Pierre McKenzie	[j46] [i7] [c39] [c38] [j21] [j20] [c18]
27	Kurt Mehlhorn	[j14]
28	Tsuyoshi Morioka	[j40]
29	Phuong Nguyen	[j47] [i11] [i8] [c37] [c36] [j42] [i5] [c34]
30	Derek C. Oppen	[c13] [c11]
31	Jan K. Pachl	[j35] [c26]
32	Nicholas Pippenger	[j13]
33	Toniann Pitassi	[i12] [c45] [j33] [c27] [j27]
34	Irwin S. Pressman	[j35] [c26]
35	Charles Rackoff	[i1] [j10]
36	Robert A. Reckhow	[j9] [c9] [j3] [c6]
37	Rüdiger Reischuk	[j19]
38	Robert Robere	[i12]
39	Walter L. Ruzzo	[j25] [j24] [c21]
40	Rahul Santhanam	[j46] [i7] [c39] [c38]
41	Ravi Sethi	[j7] [c10]
42	Michael Soltys	[j39] [c29]
43	Neil Thapen	[j41] [c35] [i3]
44	Martin Tompa	[j25] [j24] [c21]
45	Alasdair Urquhart	[j30] [c22]
46	Rutger Verbeek	[j14]
47	Dustin Wehr	[j46] [i7] [c39] [c38]
48	Tomoyuki Yamakami	[j32]
49	Yuli Ye	[c43] [i9]

Colors in the list of coauthors

Last update Fri May 24 09:28:19 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page