| Publication | Date of Publication | Type |
|---|
Extended Nullstellensatz proof systems
Proceedings of the American Mathematical Society | 2024-10-18 | Paper |
ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
The Bulletin of Symbolic Logic | 2024-04-09 | Paper |
Some consequences of cryptographical conjectures for S 2 1 and EF
Lecture Notes in Computer Science | 2023-12-12 | Paper |
| A proof complexity conjecture and the Incompleteness theorem | 2023-03-19 | Paper |
| Extended Nullstellensatz proof systems | 2023-01-25 | Paper |
INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
Journal of Symbolic Logic | 2022-06-15 | Paper |
Information in propositional proofs and algorithmic proof search
(available as arXiv preprint) | 2021-04-10 | Paper |
scientific article; zbMATH DE number 7243671 (Why is no real title available?)
(available as arXiv preprint) | 2020-09-04 | Paper |
| scientific article; zbMATH DE number 7243671 (Why is no real title available?) | 2020-09-04 | Paper |
scientific article; zbMATH DE number 7215291 (Why is no real title available?)
(available as arXiv preprint) | 2020-06-26 | Paper |
| scientific article; zbMATH DE number 7215291 (Why is no real title available?) | 2020-06-26 | Paper |
| Small circuits and dual weak PHP in the universal theory of p-time algorithms | 2020-04-24 | Paper |
A limitation on the KPT interpolation
(available as arXiv preprint) | 2020-04-06 | Paper |
| The Cook-Reckhow definition | 2019-09-09 | Paper |
Expansions of pseudoinfinite structures and circuit and proof complexity
(available as arXiv preprint) | 2019-07-24 | Paper |
Consistency of circuit lower bounds with bounded theories
(available as arXiv preprint) | 2019-05-30 | Paper |
| A proof complexity generator | 2019-04-23 | Paper |
| Proof Complexity | 2019-03-28 | Paper |
Randomized feasible interpolation and monotone circuits with a local oracle
Journal of Mathematical Logic | 2018-12-20 | Paper |
On monotone circuits with local oracles and clique lower bounds
Chicago Journal of Theoretical Computer Science | 2018-08-08 | Paper |
A feasible interpolation for random resolution
(available as arXiv preprint) | 2017-05-08 | Paper |
Unprovability of circuit upper bounds in Cook's theory PV
(available as arXiv preprint) | 2017-05-08 | Paper |
Consistency of circuit evaluation, extended resolution and total NP search problems
Forum of Mathematics, Sigma | 2016-07-06 | Paper |
A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems]
Proceedings of the American Mathematical Society | 2015-09-08 | Paper |
On the computational complexity of finding hard tautologies
Bulletin of the London Mathematical Society | 2014-03-14 | Paper |
A saturation property of structures obtained by forcing with a compact family of random variables
Archive for Mathematical Logic | 2013-02-15 | Paper |
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
Logical Methods in Computer Science | 2012-08-15 | Paper |
A note on SAT algorithms and proof complexity
Information Processing Letters | 2012-07-25 | Paper |
ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
Journal of Mathematical Logic | 2011-10-24 | Paper |
A note on propositional proof complexity of some Ramsey-type statements
Archive for Mathematical Logic | 2011-03-02 | Paper |
| scientific article; zbMATH DE number 5845490 (Why is no real title available?) | 2011-02-04 | Paper |
From feasible proofs to feasible computations
Computer Science Logic | 2010-09-03 | Paper |
A form of feasible interpolation for constant depth Frege systems
Journal of Symbolic Logic | 2010-06-24 | Paper |
Substitutions into propositional tautologies
Information Processing Letters | 2010-01-29 | Paper |
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
Journal of Symbolic Logic | 2008-05-08 | Paper |
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
Journal of Symbolic Logic | 2008-05-08 | Paper |
Consequences of the provability of NP ⊆ P/poly
Journal of Symbolic Logic | 2008-02-25 | Paper |
NP search problems in low fragments of bounded arithmetic
Journal of Symbolic Logic | 2007-07-09 | Paper |
Logical Approaches to Computational Barriers
Lecture Notes in Computer Science | 2007-04-30 | Paper |
| scientific article; zbMATH DE number 2247430 (Why is no real title available?) | 2006-01-16 | Paper |
| scientific article; zbMATH DE number 2212138 (Why is no real title available?) | 2005-10-05 | Paper |
Hardness assumptions in the foundations of theoretical computer science
Archive for Mathematical Logic | 2005-09-13 | Paper |
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
Journal of Symbolic Logic | 2005-08-29 | Paper |
Implicit proofs
Journal of Symbolic Logic | 2005-08-29 | Paper |
Approximate Euler characteristic, dimension, and weak pigeonhole principles
Journal of Symbolic Logic | 2005-08-29 | Paper |
Combinatorics of first order structures and propositional proof systems
Archive for Mathematical Logic | 2004-12-16 | Paper |
Diagonalization in proof complexity
Fundamenta Mathematicae | 2004-11-29 | Paper |
DEHN FUNCTION AND LENGTH OF PROOFS
International Journal of Algebra and Computation | 2004-05-27 | Paper |
| scientific article; zbMATH DE number 1850736 (Why is no real title available?) | 2003-04-03 | Paper |
| A Note on Conservativity Relations among Bounded Arithmetic Theories | 2002-05-29 | Paper |
On the weak pigeonhole principle
Fundamenta Mathematicae | 2002-02-21 | Paper |
On the degree of ideal membership proofs from uniform families of polynomials over a finite field
Illinois Journal of Mathematics | 2002-02-17 | Paper |
Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets.
Proceedings of the London Mathematical Society. Third Series | 2002-01-28 | Paper |
Tautologies from pseudo-random generators
The Bulletin of Symbolic Logic | 2001-09-10 | Paper |
Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings
The Bulletin of Symbolic Logic | 2001-07-05 | Paper |
Embedding logics into product logic
Studia Logica | 2001-04-19 | Paper |
Discretely ordered modules as a first-order extension of the cutting planes proof system
Journal of Symbolic Logic | 2000-02-15 | Paper |
Lifting independence results in bounded arithmetic
Archive for Mathematical Logic | 1999-11-15 | Paper |
| scientific article; zbMATH DE number 1361469 (Why is no real title available?) | 1999-11-10 | Paper |
| scientific article; zbMATH DE number 1354169 (Why is no real title available?) | 1999-10-28 | Paper |
Witnessing functions in bounded arithmetic and search problems
Journal of Symbolic Logic | 1999-08-19 | Paper |
Interpolation by a Game
Mathematical Logic Quarterly | 1999-07-05 | Paper |
| scientific article; zbMATH DE number 1136103 (Why is no real title available?) | 1998-10-19 | Paper |
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
Journal of Symbolic Logic | 1998-07-08 | Paper |
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Computational Complexity | 1998-06-29 | Paper |
| scientific article; zbMATH DE number 1163984 (Why is no real title available?) | 1998-06-11 | Paper |
Some consequences of cryptographical conjectures for \(S_2^1\) and EF
Information and Computation | 1998-05-04 | Paper |
On induction-free provability
Annals of Mathematics and Artificial Intelligence | 1997-05-13 | Paper |
| scientific article; zbMATH DE number 910748 (Why is no real title available?) | 1997-03-19 | 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 806751 (Why is no real title available?) | 1996-08-15 | Paper |
| scientific article; zbMATH DE number 819737 (Why is no real title available?) | 1995-11-23 | Paper |
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Random Structures & Algorithms | 1995-11-05 | Paper |
Lower bounds to the size of constant-depth propositional proofs
Journal of Symbolic Logic | 1994-11-03 | Paper |
An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
Proceedings of the London Mathematical Society | 1994-10-09 | Paper |
Fragments of Bounded Arithmetic and Bounded Query Classes
Transactions of the American Mathematical Society | 1994-05-23 | Paper |
| scientific article; zbMATH DE number 440477 (Why is no real title available?) | 1993-12-02 | Paper |
| scientific article; zbMATH DE number 176210 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 65749 (Why is no real title available?) | 1992-09-27 | Paper |
Bounded arithmetic and the polynomial hierarchy
Annals of Pure and Applied Logic | 1992-06-25 | Paper |
Quantified propositional calculi and fragments of bounded arithmetic
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | 1990-01-01 | Paper |
Exponentiation and second-order bounded arithmetic
Annals of Pure and Applied Logic | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4213452 (Why is no real title available?) | 1990-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 |
On the number of steps in proofs
Annals of Pure and Applied Logic | 1989-01-01 | Paper |
On the structure of initial segments of models of arithmetic
Archive for Mathematical Logic | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4104947 (Why is no real title available?) | 1989-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 |
| scientific article; zbMATH DE number 4072964 (Why is no real title available?) | 1988-01-01 | Paper |
Some Results and Problems in The Modal Set Theory MST
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | 1988-01-01 | Paper |
A note on proofs of falsehood
Archiv für Mathematische Logik und Grundlagenforschung | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4049638 (Why is no real title available?) | 1987-01-01 | Paper |
A Possible Modal Formulation of Comprehension Scheme
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | 1987-01-01 | Paper |
Some Theorems on the Lattice of Local Interpretability Types
Mathematical Logic Quarterly | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3878898 (Why is no real title available?) | 1984-01-01 | Paper |
