| Publication | Date of Publication | Type |
|---|
On the consistency of circuit lower bounds for non-deterministic time
Journal of Mathematical Logic | 2026-01-08 | Paper |
| TFNP characterizations of proof systems and monotone circuits | 2024-09-25 | Paper |
Regular resolution effectively simulates resolution
Information Processing Letters | 2024-06-07 | Paper |
On Herbrand's theorem
Lecture Notes in Computer Science | 2023-12-12 | Paper |
| On the Consistency of Circuit Lower Bounds for Non-Deterministic Time | 2023-03-02 | Paper |
scientific article; zbMATH DE number 7650825 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
Lower Bounds on OBDD Proofs with Several Orders
ACM Transactions on Computational Logic | 2022-12-08 | Paper |
Substitution and Propositional Proof Complexity
Outstanding Contributions to Logic | 2022-02-04 | Paper |
On linear resolution
Journal on Satisfiability, Boolean Modeling and Computation | 2021-12-09 | Paper |
Propositional proof systems based on maximum satisfiability
Artificial Intelligence | 2021-11-02 | Paper |
scientific article; zbMATH DE number 7350778 (Why is no real title available?)
(available as arXiv preprint) | 2021-05-25 | Paper |
| scientific article; zbMATH DE number 7350778 (Why is no real title available?) | 2021-05-25 | Paper |
Cobham recursive set functions and weak set theories
Sets and Computations | 2020-12-02 | Paper |
| scientific article; zbMATH DE number 7250156 (Why is no real title available?) | 2020-09-22 | Paper |
Expander construction in \(\mathrm{VNC}^1\)
Annals of Pure and Applied Logic | 2020-06-02 | Paper |
| DRMaxSAT with MaxHS: first contact | 2020-05-20 | Paper |
| DRAT proofs, propagation redundancy, and extended resolution | 2020-05-20 | Paper |
Short refutations for an equivalence-chain principle for constant-depth formulas
Mathematical Logic Quarterly | 2020-05-11 | Paper |
2-D Tucker is PPA complete
Journal of Computer and System Sciences | 2019-11-29 | Paper |
Feasible set functions have small circuits
Computability | 2019-10-28 | Paper |
Proof complexity of systems of (non-deterministic) decision trees and branching programs
(available as arXiv preprint) | 2019-10-18 | Paper |
Strategies for stable merge sorting
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
DRAT and Propagation Redundancy Proofs Without New Variables
(available as arXiv preprint) | 2019-09-01 | Paper |
On transformations of constant depth propositional proofs
Annals of Pure and Applied Logic | 2019-07-10 | Paper |
Short proofs of the Kneser-Lovász coloring principle
Information and Computation | 2018-06-14 | Paper |
| Expander construction in \(\mathsf{VNC}^1\) | 2018-05-03 | Paper |
Cut Elimination In Situ
Gentzen's Centenary | 2017-09-27 | Paper |
Uniform proofs of ACC representations
Archive for Mathematical Logic | 2017-09-15 | Paper |
The NP search problems of Frege and extended Frege proofs
ACM Transactions on Computational Logic | 2017-07-13 | Paper |
Resource-bounded continuity and sequentiality for type-two functionals
ACM Transactions on Computational Logic | 2017-06-13 | Paper |
Injection Structures Specified by Finite State Transducers
Computability and Complexity | 2017-04-04 | Paper |
Linear gaps between degrees for the polynomial calculus modulo distinct primes
1345.03105 | 2016-09-29 | Paper |
Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets
Journal of Symbolic Logic | 2016-08-19 | Paper |
| Towards NP-P via proof complexity and search | 2016-01-27 | Paper |
Cobham recursive set functions
Annals of Pure and Applied Logic | 2016-01-12 | Paper |
Safe recursive set functions
Journal of Symbolic Logic | 2015-11-09 | Paper |
Short proofs of the Kneser-Lovász coloring principle
Automata, Languages, and Programming | 2015-11-04 | Paper |
Short proofs of the Kneser-Lovász coloring principle
Automata, Languages, and Programming | 2015-11-04 | Paper |
Propositional proofs in Frege and extended Frege systems (abstract)
Lecture Notes in Computer Science | 2015-10-20 | Paper |
Limits on alternation trading proofs for time-space lower bounds
Computational Complexity | 2015-09-21 | Paper |
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
Transactions of the American Mathematical Society | 2015-09-08 | Paper |
Book review of: Matthias Baaz and Alexander Leitsch, Methods of cut-elimination
Studia Logica | 2015-06-26 | Paper |
Quasipolynomial size proofs of the propositional pigeonhole principle
Theoretical Computer Science | 2015-05-18 | Paper |
Sub-computable Boundedness Randomness
Logical Methods in Computer Science | 2015-01-15 | Paper |
Fragments of approximate counting
The Journal of Symbolic Logic | 2014-09-30 | Paper |
Small Stone in pool
Logical Methods in Computer Science | 2014-07-31 | Paper |
Improved separations of regular resolution from clause learning proof systems
Journal of Artificial Intelligence Research | 2014-05-16 | Paper |
Improved witnessing and local improvement principles for second-order bounded arithmetic
ACM Transactions on Computational Logic | 2014-04-16 | Paper |
Unshuffling a square is NP-hard
Journal of Computer and System Sciences | 2014-02-13 | Paper |
Alternation Trading Proofs and Their Limitations
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
An improved separation of regular resolution from pool resolution and clause learning
Theory and Applications of Satisfiability Testing – SAT 2012 | 2013-08-12 | Paper |
Probabilistic Algorithmic Randomness
Journal of Symbolic Logic | 2013-06-24 | Paper |
Propositional proofs and reductions between NP search problems
Annals of Pure and Applied Logic | 2012-07-11 | Paper |
Sharpened lower bounds for cut elimination
The Journal of Symbolic Logic | 2012-06-19 | Paper |
Sharpened lower bounds for cut elimination
The Journal of Symbolic Logic | 2012-06-19 | Paper |
Lower complexity bounds in justification logic
Annals of Pure and Applied Logic | 2012-04-10 | Paper |
Towards NP-P via proof complexity and search
Annals of Pure and Applied Logic | 2012-04-10 | Paper |
Strong isomorphism reductions in complexity theory
Journal of Symbolic Logic | 2011-12-23 | Paper |
Corrected upper bounds for free-cut elimination
Theoretical Computer Science | 2011-10-10 | Paper |
| Characterising definable search problems in bounded arithmetic via proof notations | 2011-03-09 | Paper |
The quantifier complexity of polynomial-size iterated definitions in first-order logic
Mathematical Logic Quarterly | 2011-01-10 | Paper |
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
Journal of Mathematical Logic | 2010-08-26 | Paper |
Pool resolution is NP-hard to recognize
Archive for Mathematical Logic | 2009-12-14 | Paper |
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
Logical Methods in Computer Science | 2009-04-29 | Paper |
The NP-Completeness of Reflected Fragments of Justification Logics
Logical Foundations of Computer Science | 2009-02-24 | Paper |
The NP-hardness of finding a directed acyclic graph for regular resolution
Theoretical Computer Science | 2008-05-28 | Paper |
| The computational power of bounded arithmetic from the predicative viewpoint | 2008-04-29 | Paper |
Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
Theoretical Computer Science | 2006-08-16 | Paper |
Separation results for the size of constant-depth propositional proofs
Annals of Pure and Applied Logic | 2005-09-22 | Paper |
| scientific article; zbMATH DE number 2196511 (Why is no real title available?) | 2005-08-22 | Paper |
Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis
Advances in Applied Probability | 2005-04-05 | Paper |
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
SIAM Journal on Computing | 2005-02-21 | Paper |
| scientific article; zbMATH DE number 2079024 (Why is no real title available?) | 2004-07-21 | Paper |
| 3-D Computer Graphics | 2003-10-27 | Paper |
On the computational content of intuitionistic propositional proofs
Annals of Pure and Applied Logic | 2003-04-22 | Paper |
Ordinal notations and well-orderings in bounded arithmetic
Annals of Pure and Applied Logic | 2003-03-16 | Paper |
Linear gaps between degrees for the polynomial calculus modulo distinct primes
Journal of Computer and System Sciences | 2002-03-24 | Paper |
Minimum propositional proof length is NP-hard to linearly approximate
The Journal of Symbolic Logic | 2002-01-21 | Paper |
The prospects for mathematical logic in the twenty-first century
The Bulletin of Symbolic Logic | 2001-09-10 | Paper |
The prospects for mathematical logic in the twenty-first century
The Bulletin of Symbolic Logic | 2001-09-10 | Paper |
Accurate and efficient simulation of rigid-body rotations.
Journal of Computational Physics | 2001-05-07 | Paper |
| scientific article; zbMATH DE number 1497881 (Why is no real title available?) | 2001-03-05 | Paper |
| scientific article; zbMATH DE number 1342249 (Why is no real title available?) | 2000-10-17 | Paper |
The complexity of the disjunction and existential properties in intuitionistic logic
Annals of Pure and Applied Logic | 2000-02-15 | Paper |
Good degree bounds on Nullstellensatz refutations of the induction principle
Journal of Computer and System Sciences | 1999-09-29 | Paper |
Bounded arithmetic, proof complexity and two papers of Parikh
Annals of Pure and Applied Logic | 1999-06-24 | Paper |
| scientific article; zbMATH DE number 1215493 (Why is no real title available?) | 1999-05-16 | Paper |
| scientific article; zbMATH DE number 1215494 (Why is no real title available?) | 1999-05-04 | Paper |
| scientific article; zbMATH DE number 1222561 (Why is no real title available?) | 1999-03-02 | Paper |
| scientific article; zbMATH DE number 1223618 (Why is no real title available?) | 1998-11-15 | 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 1114017 (Why is no real title available?) | 1998-06-24 | Paper |
Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
SIAM Journal on Computing | 1998-05-10 | Paper |
| scientific article; zbMATH DE number 1088188 (Why is no real title available?) | 1997-11-17 | Paper |
| scientific article; zbMATH DE number 1070621 (Why is no real title available?) | 1997-10-07 | Paper |
| scientific article; zbMATH DE number 1003236 (Why is no real title available?) | 1997-06-01 | Paper |
Cutting planes, connectivity, and threshold logic
Archive for Mathematical Logic | 1996-07-16 | Paper |
Some remarks on lengths of propositional proofs
Archive for Mathematical Logic | 1996-07-16 | Paper |
Unprovability of consistency statements in fragments of bounded arithmetic
Annals of Pure and Applied Logic | 1996-03-31 | Paper |
| scientific article; zbMATH DE number 806744 (Why is no real title available?) | 1995-10-17 | Paper |
| scientific article; zbMATH DE number 806745 (Why is no real title available?) | 1995-10-17 | Paper |
Relating the bounded arithmetic and polynomial time hierarchies
Annals of Pure and Applied Logic | 1995-10-04 | Paper |
| scientific article; zbMATH DE number 733384 (Why is no real title available?) | 1995-03-30 | Paper |
The Serial Transitive Closure Problem for Trees
SIAM Journal on Computing | 1995-03-27 | Paper |
On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
Journal of Symbolic Logic | 1994-11-27 | Paper |
An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
Proceedings of the London Mathematical Society | 1994-10-09 | Paper |
| scientific article; zbMATH DE number 619542 (Why is no real title available?) | 1994-09-13 | Paper |
| scientific article; zbMATH DE number 440476 (Why is no real title available?) | 1994-08-16 | Paper |
Size-depth tradeoffs for Boolean formulae
Information Processing Letters | 1994-04-05 | Paper |
| scientific article; zbMATH DE number 440477 (Why is no real title available?) | 1993-12-02 | Paper |
| scientific article; zbMATH DE number 432703 (Why is no real title available?) | 1993-11-11 | Paper |
The deduction rule and linear and near-linear proof simulations
Journal of Symbolic Logic | 1993-10-24 | Paper |
Intuitionistic validity in \(T\)-normal Kripke structures
Annals of Pure and Applied Logic | 1993-09-22 | Paper |
| scientific article; zbMATH DE number 176198 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 149060 (Why is no real title available?) | 1993-04-01 | Paper |
An Optimal Parallel Algorithm for Formula Evaluation
SIAM Journal on Computing | 1993-01-16 | Paper |
The graph of multiplication is equivalent to counting
Information Processing Letters | 1992-09-26 | Paper |
On truth-table reducibility to SAT
Information and Computation | 1992-06-25 | Paper |
Propositional consistency proofs
Annals of Pure and Applied Logic | 1992-06-25 | Paper |
The undecidability of \(k\)-provability
Annals of Pure and Applied Logic | 1992-06-25 | Paper |
The modal logic of pure provability
Notre Dame Journal of Formal Logic | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4145897 (Why is no real title available?) | 1990-01-01 | Paper |
Resolution proofs of generalized pigeonhole principles
Theoretical Computer Science | 1988-01-01 | Paper |
Polynomial size proofs of the propositional pigeonhole principle
Journal of Symbolic Logic | 1987-01-01 | Paper |
| A Conservation Result Concerning Bounded Theories and the Collection Axiom | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4059391 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4066875 (Why is no real title available?) | 1986-01-01 | Paper |
