☰

Stephen Arthur Cook, Ph.D. - Publications

Affiliations: 
Computer Science University of Toronto, Toronto, ON, Canada 
Area:
complexity theory, proof complexity, P vs NP
Tree Info Similar researchers PubMed Report error

40 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2014 Cook SA, Filmus Y, Lê DTM. The complexity of the comparator circuit value problem Acm Transactions On Computation Theory. 6. DOI: 10.1145/2635822  0.368
2012 Cook S, Fontes L. Formal theories for linear algebra Logical Methods in Computer Science. 8. DOI: 10.2168/Lmcs-8(1:25)2012  0.31
2012 Kawamura A, Cook S. Complexity theory for operators in analysis Acm Transactions On Computation Theory. 4. DOI: 10.1145/2189778.2189780  0.379
2012 Cook S, McKenzie P, Wehr D, Braverman M, Santhanam R. Pebbles and branching programs for tree evaluation Acm Transactions On Computation Theory. 3. DOI: 10.1145/2077336.2077337  0.561
2012 Nguyen P, Cook S. The complexity of proving the discrete jordan curve theorem Acm Transactions On Computational Logic. 13. DOI: 10.1145/2071368.2071377  0.339
2009 Braverman M, Cook S, McKenzie P, Santhanam R, Wehr D. Fractional pebbling and thrifty branching programs Leibniz International Proceedings in Informatics, Lipics. 4: 109-120. DOI: 10.4230/LIPIcs.FSTTCS.2009.2311  0.478
2009 Braverman M, Cook S, McKenzie P, Santhanam R, Wehr D. Branching programs for tree evaluation Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5734: 175-186. DOI: 10.1007/978-3-642-03816-7_16  0.521
2006 Nguyen P, Cook SA. Theories for TC0 and Other Small Complexity Classes Logical Methods in Computer Science. 2. DOI: 10.2168/Lmcs-2(1:3)2006  0.365
2006 Cook S, Thapen N. The strength of replacement in weak arithmetic Acm Transactions On Computational Logic. 7: 749-764. DOI: 10.1145/1183278.1183283  0.33
2006 Braverman M, Cook S. Computing over the reals: Foundations for scientific computing Notices of the American Mathematical Society. 53: 318-329.  0.49
2004 Soltys M, Cook S. The proof complexity of linear algebra Annals of Pure and Applied Logic. 130: 277-323. DOI: 10.1016/J.Apal.2003.10.018  0.321
2003 Cook S. The importance of the P versus NP question Journal of the Acm. 50: 27-29. DOI: 10.1145/602382.602398  0.355
2003 Cook S, Kolokolova A. A second-order system for polytime reasoning based on Grädel's theorem Annals of Pure and Applied Logic. 124: 193-231. DOI: 10.1016/S0168-0072(03)00056-3  0.31
2002 Cook SA, Pachl J, Pressman IS. The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy Distributed Computing. 15: 57-66. DOI: 10.1007/S446-002-8031-5  0.305
1999 Cook S. Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 (1991), pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 (1995), pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic , vol. 61 (1996), pp. 942–966. Journal of Symbolic Logic. 64: 1821-1823. DOI: 10.2307/2586815  0.322
1998 Beame P, Cook S, Edmonds J, Impagliazzo R, Pitassi T. The Relative Complexity of NP Search Problems Journal of Computer and System Sciences. 57: 3-19. DOI: 10.1006/Jcss.1998.1575  0.331
1996 Kapron BM, Cook SA. A New Characterization of Type-2 Feasibility Siam Journal On Computing. 25: 117-132. DOI: 10.1137/S0097539794263452  0.33
1993 Cook S, Urquhart A. Functional interpretations of feasibly constructive arithmetic Annals of Pure and Applied Logic. 63: 103-200. DOI: 10.1016/0168-0072(93)90044-E  0.316
1993 Cook SA, Dymond PW. Parallel pointer machines Computational Complexity. 3: 19-30. DOI: 10.1007/Bf01200405  0.3
1992 Bellantoni S, Cook S. A new recursion-theoretic characterization of the polytime functions Computational Complexity. 2: 97-110. DOI: 10.1007/Bf01201998  0.337
1989 Borodin A, Cook SA, Dymond PW, Ruzzo WL, Tompa M. Two Applications of Inductive Counting for Complementation Problems Siam Journal On Computing. 18: 559-578. DOI: 10.1137/0218038  0.411
1989 Dymond PW, Cook SA. Complexity theory of parallel time and hardware Information & Computation. 80: 205-226. DOI: 10.1016/0890-5401(89)90009-6  0.319
1988 Cook SA. Short propositional formulas represent nondeterministic computations Information Processing Letters. 26: 269-270. DOI: 10.1016/0020-0190(88)90152-4  0.308
1988 Cook SA, Luby M. A simple parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula Information Processing Letters. 27: 141-145. DOI: 10.1016/0020-0190(88)90069-5  0.336
1987 McKenzie P, Cook SA. The parallel complexity of Abelian permutation group problems Siam Journal On Computing. 16: 880-909. DOI: 10.1137/0216058  0.351
1987 Cook SA, McKenzie P. Problems complete for deterministic logarithmic space Journal of Algorithms. 8: 385-394. DOI: 10.1016/0196-6774(87)90018-6  0.332
1986 Beame PW, Cook SA, Hoover HJ. Log depth circuits for division and related problems Siam Journal On Computing. 15: 994-1003. DOI: 10.1137/0215070  0.304
1986 Cook S, Dwork C, duml R, Reischuk g. Upper and lower time bounds for parallel random access machines without simultaneous writes Siam Journal On Computing. 15: 87-97. DOI: 10.1137/0215006  0.346
1985 Cook SA. A taxonomy of problems with fast parallel algorithms Information and Control. 64: 2-22. DOI: 10.1016/S0019-9958(85)80041-3  0.372
1983 Cook SA. An overview of computational complexity Communications of the Acm. 26: 400-408. DOI: 10.1145/358141.358144  0.349
1983 Borodin A, Cook S, Pippenger N. Parallel computation for well-endowed rings and space-bounded probabilistic machines Information and Control. 58: 113-136. DOI: 10.1016/S0019-9958(83)80060-6  0.335
1982 Borodin A, Cook SA. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation Siam Journal On Computing. 11: 287-297. DOI: 10.1137/0211022  0.333
1980 Cook SA, Rackoff CW. Space Lower Bounds for Maze Threadability on Restricted Machines Siam Journal On Computing. 9: 636-652. DOI: 10.1137/0209048  0.32
1976 Borodin A, Cook SA. On the Number of Additions to Compute Specific Polynomials Siam Journal On Computing. 5: 146-157. DOI: 10.1137/0205013  0.351
1976 Cook S, Sethi R. Storage requirements for deterministic polynomialtime recognizable languages Journal of Computer and System Sciences. 13: 25-37. DOI: 10.1016/S0022-0000(76)80048-7  0.302
1974 Cook SA. An observation on time-storage trade off Journal of Computer and System Sciences. 9: 308-316. DOI: 10.1016/S0022-0000(74)80046-2  0.316
1971 Cook SA. Bečvář Jiří. Real-time and complexity problems in automata theory. English with Czech summary. Kybernetika (Prague), vol. 1 (1965), pp. 475–498. Journal of Symbolic Logic. 36: 346-346. DOI: 10.2307/2270318  0.322
1971 Cook SA. Characterizations of Pushdown Machines in Terms of Time-Bounded Computers Journal of the Acm. 18: 4-18. DOI: 10.1145/321623.321625  0.312
1969 Cook SA. Blum Manuel. A Machine-independent theory of the complexity of recursive functions. Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336. Journal of Symbolic Logic. 34: 657-658. DOI: 10.2307/2270887  0.322
1969 Cook SA, Aanderaa SO. On The Minimum Computation Time Of Functions Transactions of the American Mathematical Society. 142: 291-314. DOI: 10.1090/S0002-9947-1969-0249212-8  0.312
Show low-probability matches.