| Publication | Date of Publication | Type |
|---|
| Linear branching programs and directional affine extractors | 2024-07-05 | Paper |
Logic, Automata, and Computational Complexity: The Works Of Stephen A. Cook. Edited by Bruce M. Kapron, ACM Books, vol. 43. Association for Computing Machinery, New York, xxvi + 398 pp.—therein: - Michelle Waitzman. Stephen Cook: Complexity’s Humble Hero, pp. 3–28. - Bruce M. Kapron and Stephen A. Cook, ACM Interview of Stephen A. Cook by Bruce M. Kapron, pp. 29–44. - Stephen A. Cook, Overview of Computational Complexity, pp. 47–70. - Christos H. Papadimitriou, …
The Bulletin of Symbolic Logic | 2024-02-23 | Paper |
On sparse parity check matrices (extended abstract)
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Some consequences of cryptographical conjectures for S 2 1 and EF
Lecture Notes in Computer Science | 2023-12-12 | Paper |
| scientific article; zbMATH DE number 7675626 (Why is no real title available?) | 2023-04-18 | Paper |
| Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters | 2023-02-23 | Paper |
| On the Ramsey number of daisies I | 2022-11-18 | Paper |
Extractors for small zero-fixing sources
Combinatorica | 2022-11-09 | Paper |
On matrices potentially useful for tree codes
Information Processing Letters | 2021-12-14 | Paper |
Classification of 9-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\)
Finite Fields and their Applications | 2021-02-19 | Paper |
The canonical pairs of bounded depth Frege systems
Annals of Pure and Applied Logic | 2020-12-15 | Paper |
On matrices potentially useful for tree codes
(available as arXiv preprint) | 2020-12-05 | Paper |
Santha-Vazirani sources, deterministic condensers and very strong extractors
Theory of Computing Systems | 2020-08-26 | Paper |
| Reflection principles, propositional proof systems, and theories | 2020-07-29 | Paper |
Tighter hard instances for PPSZ
(available as arXiv preprint) | 2020-05-27 | Paper |
| Random resolution refutations | 2020-05-26 | Paper |
| Representations of monotone Boolean functions by linear programs | 2020-05-26 | Paper |
A wild model of linear arithmetic and discretely ordered modules
Mathematical Logic Quarterly | 2020-04-29 | Paper |
Randomness, pseudorandomness and models of arithmetic
(available as arXiv preprint) | 2020-03-30 | Paper |
Representations of monotone Boolean functions by linear programs
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
| Abel Prize. The highest award for mathematics | 2019-10-23 | Paper |
Random resolution refutations
Computational Complexity | 2019-07-10 | Paper |
| scientific article; zbMATH DE number 7075925 (Why is no real title available?) | 2019-07-03 | Paper |
Unexpected upper bounds on the complexity of some communication games
Automata, Languages and Programming | 2019-04-29 | Paper |
Extractors for small zero-fixing sources
(available as arXiv preprint) | 2019-04-16 | Paper |
Incompleteness in the finite domain
The Bulletin of Symbolic Logic | 2018-05-17 | Paper |
The complexity of proving that a graph is Ramsey
Combinatorica | 2018-03-16 | Paper |
| Beating brute force for (quantified) satisfiability of circuits of bounded treewidth | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6829289 (Why is no real title available?) | 2018-01-24 | Paper |
A note on monotone real circuits
Information Processing Letters | 2017-12-13 | Paper |
Partition expanders
Theory of Computing Systems | 2017-07-17 | Paper |
| Metamathematics of first-order arithmetic | 2017-07-06 | Paper |
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Partition expanders
(available as arXiv preprint) | 2017-03-03 | Paper |
On the joint entropy of \(d\)-wise-independent variables.
Commentationes Mathematicae Universitatis Carolinae | 2017-01-13 | Paper |
On the computational power of depth 2 circuits with threshold and modulo gates
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
A note on the use of determinant for proving lower bounds on the size of linear circuits
Information Processing Letters | 2016-06-16 | Paper |
Linear tree codes and the problem of explicit constructions
Linear Algebra and its Applications | 2015-12-18 | Paper |
On the complexity of finding falsifying assignments for Herbrand disjunctions
Archive for Mathematical Logic | 2015-11-18 | Paper |
Classification of 8-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\)
Communications in Algebra | 2015-08-11 | Paper |
Modified ranks of tensors and the size of circuits
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
On the complexity of circuit satisfiability
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Parity Games and Propositional Proofs
ACM Transactions on Computational Logic | 2014-07-17 | Paper |
Pseudorandom generators for group products
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Parity Games and Propositional Proofs
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
The complexity of proving that a graph is Ramsey
Lecture Notes in Computer Science | 2013-08-06 | Paper |
| scientific article; zbMATH DE number 6152292 (Why is no real title available?) | 2013-04-09 | Paper |
Logical foundations of mathematics and computational complexity. A gentle introduction
Springer Monographs in Mathematics | 2013-04-08 | Paper |
| On extracting computations from propositional proofs (a survey) | 2012-08-29 | Paper |
A lower bound on the size of resolution proofs of the Ramsey theorem
Information Processing Letters | 2012-07-25 | Paper |
Alternating minima and maxima, Nash equilibria and bounded arithmetic
Annals of Pure and Applied Logic | 2012-03-13 | Paper |
| scientific article; zbMATH DE number 5896225 (Why is no real title available?) | 2011-05-18 | Paper |
| Decorated linear order types and the theory of concatenation | 2011-03-02 | Paper |
Bounded-depth circuits
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Some constructive bounds on Ramsey numbers
Journal of Combinatorial Theory. Series B | 2010-06-03 | Paper |
On convex complexity measures
Theoretical Computer Science | 2010-04-15 | Paper |
A note on monotone complexity and the rank of matrices
Information Processing Letters | 2009-04-28 | Paper |
Solving the \$100 modal logic challenge
Journal of Applied Logic | 2009-03-25 | Paper |
Quantum deduction rules
Annals of Pure and Applied Logic | 2009-02-19 | Paper |
Fragments of bounded arithmetic and the lengths of proofs
Journal of Symbolic Logic | 2009-01-09 | Paper |
An improved exponential-time algorithm for k -SAT
Journal of the ACM | 2008-12-21 | Paper |
MaLARea SG1 - Machine Learner for Automated Reasoning with Semantic Guidance
Automated Reasoning | 2008-11-27 | Paper |
Twelve Problems in Proof Complexity
Computer Science – Theory and Applications | 2008-06-05 | Paper |
On Search Problems in Complexity Theory and in Logic (Abstract)
Lecture Notes in Computer Science | 2007-05-02 | Paper |
| scientific article; zbMATH DE number 5130817 (Why is no real title available?) | 2007-03-05 | Paper |
| scientific article; zbMATH DE number 5038466 (Why is no real title available?) | 2006-07-03 | Paper |
| scientific article; zbMATH DE number 2196516 (Why is no real title available?) | 2005-08-22 | Paper |
| scientific article; zbMATH DE number 2187726 (Why is no real title available?) | 2005-07-20 | Paper |
An Application of Hindman's Theorem to a Problem on Communication Complexity
Combinatorics, Probability and Computing | 2005-03-08 | Paper |
Parallel strategies
Journal of Symbolic Logic | 2005-02-09 | Paper |
| scientific article; zbMATH DE number 2079024 (Why is no real title available?) | 2004-07-21 | Paper |
Equilateral sets in \(l_p^n\)
Geometric and Functional Analysis. GAFA | 2003-09-01 | Paper |
On reducibility and symmetry of disjoint NP pairs.
Theoretical Computer Science | 2003-08-17 | Paper |
Monotone simulations of non-monotone proofs.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
On the computational content of intuitionistic propositional proofs
Annals of Pure and Applied Logic | 2003-04-22 | Paper |
Complexity theory and genetics: The computational power of crossing over
Information and Computation | 2003-01-14 | Paper |
| scientific article; zbMATH DE number 1834681 (Why is no real title available?) | 2002-11-25 | Paper |
Cycles of nonzero elements in low rank matrices
Combinatorica | 2002-10-20 | Paper |
Constructive lower bounds for off-diagonal Ramsey numbers
Israel Journal of Mathematics | 2002-06-24 | Paper |
Proofs as Games
American Mathematical Monthly | 2001-11-26 | Paper |
Some structural properties of low-rank matrices related to computational complexity
Theoretical Computer Science | 2000-06-04 | Paper |
scientific article; zbMATH DE number 1452705 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2000-05-29 | Paper |
| scientific article; zbMATH DE number 1445296 (Why is no real title available?) | 2000-05-10 | Paper |
Computing Boolean functions by polynomials and threshold circuits
Computational Complexity | 2000-04-17 | Paper |
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
Computational Complexity | 2000-03-30 | Paper |
| scientific article; zbMATH DE number 1390276 (Why is no real title available?) | 2000-01-17 | Paper |
| scientific article; zbMATH DE number 1354169 (Why is no real title available?) | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1306901 (Why is no real title available?) | 1999-08-31 | Paper |
A note on applicability of the incompleteness theorem to human mind
Annals of Pure and Applied Logic | 1999-06-24 | Paper |
| scientific article; zbMATH DE number 1222558 (Why is no real title available?) | 1999-03-02 | Paper |
On sparse parity check matrices
Designs, Codes and Cryptography | 1998-12-13 | Paper |
| scientific article; zbMATH DE number 1215500 (Why is no real title available?) | 1998-12-08 | Paper |
On the computational power of depth-2 circuits with threshold and modulo gates
Theoretical Computer Science | 1998-10-22 | Paper |
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Computational Complexity | 1998-06-29 | Paper |
Some consequences of cryptographical conjectures for \(S_2^1\) and EF
Information and Computation | 1998-05-04 | Paper |
| scientific article; zbMATH DE number 1144041 (Why is no real title available?) | 1998-04-20 | Paper |
| scientific article; zbMATH DE number 1114028 (Why is no real title available?) | 1998-03-01 | Paper |
Lower bounds for resolution and cutting plane proofs and monotone computations
Journal of Symbolic Logic | 1997-12-17 | Paper |
| scientific article; zbMATH DE number 981682 (Why is no real title available?) | 1997-08-03 | Paper |
Boolean Circuits, Tensor Ranks, and Communication Complexity
SIAM Journal on Computing | 1997-05-26 | Paper |
| scientific article; zbMATH DE number 910749 (Why is no real title available?) | 1997-02-09 | Paper |
Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
Proceedings of the London Mathematical Society | 1996-12-05 | Paper |
| scientific article; zbMATH DE number 922617 (Why is no real title available?) | 1996-09-01 | Paper |
| scientific article; zbMATH DE number 849963 (Why is no real title available?) | 1996-08-22 | Paper |
Top-down lower bounds for depth-three circuits
Computational Complexity | 1996-01-07 | Paper |
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Random Structures & Algorithms | 1995-11-05 | Paper |
Some combinatorial-algebraic problems from complexity theory
Discrete Mathematics | 1995-02-13 | Paper |
Communication in bounded depth circuits
Combinatorica | 1994-08-11 | Paper |
| scientific article; zbMATH DE number 522838 (Why is no real title available?) | 1994-06-26 | Paper |
| scientific article; zbMATH DE number 495970 (Why is no real title available?) | 1994-06-05 | Paper |
Superconcentrators of depths 2 and 3; odd levels help (rarely)
Journal of Computer and System Sciences | 1994-04-27 | Paper |
| scientific article; zbMATH DE number 512985 (Why is no real title available?) | 1994-04-07 | Paper |
| scientific article; zbMATH DE number 440480 (Why is no real title available?) | 1993-12-05 | Paper |
| scientific article; zbMATH DE number 440474 (Why is no real title available?) | 1993-12-02 | Paper |
On shifting networks
Theoretical Computer Science | 1993-10-17 | Paper |
| scientific article; zbMATH DE number 227056 (Why is no real title available?) | 1993-07-06 | Paper |
Threshold circuits of bounded depth
Journal of Computer and System Sciences | 1993-06-29 | Paper |
A combinatorial approach to complexity
Combinatorica | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 65757 (Why is no real title available?) | 1992-09-27 | Paper |
| scientific article; zbMATH DE number 37868 (Why is no real title available?) | 1992-06-28 | Paper |
| scientific article; zbMATH DE number 17538 (Why is no real title available?) | 1992-06-26 | Paper |
Bounded arithmetic and the polynomial hierarchy
Annals of Pure and Applied Logic | 1992-06-25 | Paper |
| scientific article; zbMATH DE number 4213452 (Why is no real title available?) | 1990-01-01 | Paper |
On equational theories of semilattices with operators
Bulletin of the Australian Mathematical Society | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4200143 (Why is no real title available?) | 1990-01-01 | Paper |
Lower bounds to the complexity of symmetric Boolean functions
Theoretical Computer Science | 1990-01-01 | Paper |
Quantified propositional calculi and fragments of bounded arithmetic
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | 1990-01-01 | Paper |
A note on bounded arithmetic
Fundamenta Mathematicae | 1990-01-01 | Paper |
A lattice of chapters of mathematics (interpretations between theorems [theories)]
Memoirs of the American Mathematical Society | 1990-01-01 | Paper |
On the structure of initial segments of models of arithmetic
Archive for Mathematical Logic | 1989-01-01 | Paper |
Propositional proof systems, the consistency of first order theories and the complexity of computations
Journal of Symbolic Logic | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4118416 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4055034 (Why is no real title available?) | 1988-01-01 | Paper |
The number of proof lines and the size of proofs in first order logic
Archive for Mathematical Logic | 1988-01-01 | Paper |
Graph complexity
Acta Informatica | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4085639 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4045650 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4033740 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4004177 (Why is no real title available?) | 1986-01-01 | Paper |
Cuts, consistency statements and interpretations
Journal of Symbolic Logic | 1985-01-01 | Paper |
On congruence lattices of lattices
Algebra Universalis | 1985-01-01 | Paper |
Elementary Extensions of Models of the Alternative Set Theory
Mathematical Logic Quarterly | 1985-01-01 | Paper |
Models of the alternative set theory
Journal of Symbolic Logic | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3913677 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3952498 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3877162 (Why is no real title available?) | 1984-01-01 | Paper |
Some Prime Elements in the Lattice of Interpretability Types
Transactions of the American Mathematical Society | 1983-01-01 | Paper |
Regraphs and congruence lattices
Algebra Universalis | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3845576 (Why is no real title available?) | 1983-01-01 | Paper |
Partition theorems for systems of finite subsets of integers
Discrete Mathematics | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3780579 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3737634 (Why is no real title available?) | 1980-01-01 | Paper |
Every finite lattice can be embedded in a finite partition lattice
Algebra Universalis | 1980-01-01 | Paper |
Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups
Algebra Universalis | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3670493 (Why is no real title available?) | 1979-01-01 | Paper |
Complexity in mechanized hypothesis formation
Theoretical Computer Science | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3565052 (Why is no real title available?) | 1977-01-01 | Paper |
| scientific article; zbMATH DE number 3637849 (Why is no real title available?) | 1977-01-01 | Paper |
Distributivity of strongly representable lattices
Algebra Universalis | 1977-01-01 | Paper |
| scientific article; zbMATH DE number 3557835 (Why is no real title available?) | 1976-01-01 | Paper |
A new proof of the congruence lattice representation theorem
Algebra Universalis | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3499250 (Why is no real title available?) | 1975-01-01 | Paper |
| scientific article; zbMATH DE number 3485739 (Why is no real title available?) | 1975-01-01 | Paper |
Colorings of $k$-sets with low discrepancy on small sets
(available as arXiv preprint) | N/A | Paper |
