| 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, … | 2024-02-23 | Paper |
| On sparse parity check matrices (extended abstract) | 2024-01-29 | Paper |
| Some consequences of cryptographical conjectures for S 2 1 and EF | 2023-12-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5887286 | 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 | 2022-11-09 | Paper |
| On matrices potentially useful for tree codes | 2021-12-14 | Paper |
| Classification of 9-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\) | 2021-02-19 | Paper |
| The canonical pairs of bounded depth Frege systems | 2020-12-15 | Paper |
| On matrices potentially useful for tree codes | 2020-12-05 | Paper |
| Santha-Vazirani sources, deterministic condensers and very strong extractors | 2020-08-26 | Paper |
| Reflection principles, propositional proof systems, and theories | 2020-07-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111416 | 2020-05-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111131 | 2020-05-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111133 | 2020-05-26 | Paper |
| A wild model of linear arithmetic and discretely ordered modules | 2020-04-29 | Paper |
| Randomness, pseudorandomness and models of arithmetic | 2020-03-30 | Paper |
| Representations of Monotone Boolean Functions by Linear Programs | 2019-12-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5239861 | 2019-10-23 | Paper |
| Random resolution refutations | 2019-07-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4967225 | 2019-07-03 | Paper |
| Unexpected upper bounds on the complexity of some communication games | 2019-04-29 | Paper |
| Extractors for small zero-fixing sources | 2019-04-16 | Paper |
| INCOMPLETENESS IN THE FINITE DOMAIN | 2018-05-17 | Paper |
| The complexity of proving that a graph is Ramsey | 2018-03-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4607895 | 2018-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601841 | 2018-01-24 | Paper |
| A note on monotone real circuits | 2017-12-13 | Paper |
| Partition expanders | 2017-07-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5273442 | 2017-07-06 | Paper |
| Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates | 2017-06-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2965495 | 2017-03-03 | Paper |
| On the joint entropy of $d$-wise-independent variables | 2017-01-13 | Paper |
| On the computational power of depth 2 circuits with threshold and modulo gates | 2016-09-01 | Paper |
| A note on the use of determinant for proving lower bounds on the size of linear circuits | 2016-06-16 | Paper |
| Linear tree codes and the problem of explicit constructions | 2015-12-18 | Paper |
| On the complexity of finding falsifying assignments for Herbrand disjunctions | 2015-11-18 | Paper |
| Classification of 8-Dimensional Trilinear Alternating Forms over GF(2) | 2015-08-11 | Paper |
| Modified ranks of tensors and the size of circuits | 2015-05-07 | Paper |
| On the complexity of circuit satisfiability | 2014-08-13 | Paper |
| Parity Games and Propositional Proofs | 2014-07-17 | Paper |
| Pseudorandom generators for group products | 2014-06-05 | Paper |
| Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates | 2014-05-13 | Paper |
| Parity Games and Propositional Proofs | 2013-09-20 | Paper |
| The complexity of proving that a graph is Ramsey | 2013-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4913801 | 2013-04-09 | Paper |
| Logical Foundations of Mathematics and Computational Complexity | 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 | 2012-07-25 | Paper |
| Alternating minima and maxima, Nash equilibria and bounded arithmetic | 2012-03-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2998376 | 2011-05-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3079690 | 2011-03-02 | Paper |
| Bounded-depth circuits | 2010-08-16 | Paper |
| Some constructive bounds on Ramsey numbers | 2010-06-03 | Paper |
| On convex complexity measures | 2010-04-15 | Paper |
| A note on monotone complexity and the rank of matrices | 2009-04-28 | Paper |
| Solving the \$100 modal logic challenge | 2009-03-25 | Paper |
| Quantum deduction rules | 2009-02-19 | Paper |
| Fragments of bounded arithmetic and the lengths of proofs | 2009-01-09 | Paper |
| An improved exponential-time algorithm for k -SAT | 2008-12-21 | Paper |
| MaLARea SG1 - Machine Learner for Automated Reasoning with Semantic Guidance | 2008-11-27 | Paper |
| Twelve Problems in Proof Complexity | 2008-06-05 | Paper |
| On Search Problems in Complexity Theory and in Logic (Abstract) | 2007-05-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3424881 | 2007-03-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5477362 | 2006-07-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5465363 | 2005-08-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5460925 | 2005-07-20 | Paper |
| An Application of Hindman's Theorem to a Problem on Communication Complexity | 2005-03-08 | Paper |
| Parallel strategies | 2005-02-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474836 | 2004-07-21 | Paper |
| Equilateral sets in \(l_p^n\) | 2003-09-01 | Paper |
| On reducibility and symmetry of disjoint NP pairs. | 2003-08-17 | Paper |
| Monotone simulations of non-monotone proofs. | 2003-05-14 | Paper |
| On the computational content of intuitionistic propositional proofs | 2003-04-22 | Paper |
| Complexity theory and genetics: The computational power of crossing over | 2003-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4779177 | 2002-11-25 | Paper |
| Cycles of nonzero elements in low rank matrices | 2002-10-20 | Paper |
| Constructive lower bounds for off-diagonal Ramsey numbers | 2002-06-24 | Paper |
| Proofs as Games | 2001-11-26 | Paper |
| Some structural properties of low-rank matrices related to computational complexity | 2000-06-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4484662 | 2000-05-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4952609 | 2000-05-10 | Paper |
| Computing Boolean functions by polynomials and threshold circuits | 2000-04-17 | Paper |
| Lower bounds for the polynomial calculus and the Gröbner basis algorithm | 2000-03-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4934563 | 2000-01-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4268484 | 1999-10-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252754 | 1999-08-31 | Paper |
| A note on applicability of the incompleteness theorem to human mind | 1999-06-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218095 | 1999-03-02 | Paper |
| On sparse parity check matrices | 1998-12-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4215637 | 1998-12-08 | Paper |
| On the computational power of depth-2 circuits with threshold and modulo gates | 1998-10-22 | Paper |
| Proof complexity in algebraic systems and bounded depth Frege systems with modular counting | 1998-06-29 | Paper |
| Some consequences of cryptographical conjectures for \(S_2^1\) and EF | 1998-05-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4384146 | 1998-04-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4375799 | 1998-03-01 | Paper |
| Lower bounds for resolution and cutting plane proofs and monotone computations | 1997-12-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2785569 | 1997-08-03 | Paper |
| Boolean Circuits, Tensor Ranks, and Communication Complexity | 1997-05-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4885911 | 1997-02-09 | Paper |
| Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs | 1996-12-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4893137 | 1996-09-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4865977 | 1996-08-22 | Paper |
| Top-down lower bounds for depth-three circuits | 1996-01-07 | Paper |
| An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle | 1995-11-05 | Paper |
| Some combinatorial-algebraic problems from complexity theory | 1995-02-13 | Paper |
| Communication in bounded depth circuits | 1994-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4284231 | 1994-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4277629 | 1994-06-05 | Paper |
| Superconcentrators of depths 2 and 3; odd levels help (rarely) | 1994-04-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281694 | 1994-04-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3140637 | 1993-12-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3140631 | 1993-12-02 | Paper |
| On shifting networks | 1993-10-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5286672 | 1993-07-06 | Paper |
| Threshold circuits of bounded depth | 1993-06-29 | Paper |
| A combinatorial approach to complexity | 1993-01-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4010368 | 1992-09-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3990226 | 1992-06-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3974862 | 1992-06-26 | Paper |
| Bounded arithmetic and the polynomial hierarchy | 1992-06-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3359762 | 1990-01-01 | Paper |
| On equational theories of semilattices with operators | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3348859 | 1990-01-01 | Paper |
| Lower bounds to the complexity of symmetric Boolean functions | 1990-01-01 | Paper |
| Quantified propositional calculi and fragments of bounded arithmetic | 1990-01-01 | Paper |
| A note on bounded arithmetic | 1990-01-01 | Paper |
| A lattice of chapters of mathematics (interpretations between theorems [theories]) | 1990-01-01 | Paper |
| On the structure of initial segments of models of arithmetic | 1989-01-01 | Paper |
| Propositional proof systems, the consistency of first order theories and the complexity of computations | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4732500 | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3790651 | 1988-01-01 | Paper |
| The number of proof lines and the size of proofs in first order logic | 1988-01-01 | Paper |
| Graph complexity | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3815293 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3783219 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3773878 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3755452 | 1986-01-01 | Paper |
| Cuts, consistency statements and interpretations | 1985-01-01 | Paper |
| On congruence lattices of lattices | 1985-01-01 | Paper |
| Elementary Extensions of Models of the Alternative Set Theory | 1985-01-01 | Paper |
| Models of the alternative set theory | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3690219 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3722269 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3344188 | 1984-01-01 | Paper |
| Some Prime Elements in the Lattice of Interpretability Types | 1983-01-01 | Paper |
| Regraphs and congruence lattices | 1983-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3315507 | 1983-01-01 | Paper |
| Partition theorems for systems of finite subsets of integers | 1982-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3959443 | 1982-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3924175 | 1980-01-01 | Paper |
| Every finite lattice can be embedded in a finite partition lattice | 1980-01-01 | Paper |
| Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups | 1980-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3867848 | 1979-01-01 | Paper |
| Complexity in mechanized hypothesis formation | 1979-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4137224 | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4198747 | 1977-01-01 | Paper |
| Distributivity of strongly representable lattices | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4133670 | 1976-01-01 | Paper |
| A new proof of the congruence lattice representation theorem | 1976-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4080749 | 1975-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4068695 | 1975-01-01 | Paper |
| Colorings of $k$-sets with low discrepancy on small sets | N/A | Paper |
