| Publication | Date of Publication | Type |
|---|
On the consistency of circuit lower bounds for non-deterministic time
Journal of Mathematical Logic | 2026-01-08 | Paper |
| Automating resolution is NP-hard | 2025-08-12 | Paper |
A parameterized halting problem, _0 truth and the MRDP theorem
The Journal of Symbolic Logic | 2025-07-24 | Paper |
Jan Krajìček, Proof Complexity, Encyclopedia of Mathematics and Its Applications, no. 170, Cambridge University Press, Cambridge, UK, 2019, xvi + 516 pp.
The Bulletin of Symbolic Logic | 2023-08-10 | Paper |
| A surprising relationship between descriptive complexity and proof complexity | 2023-06-26 | Paper |
| On the Consistency of Circuit Lower Bounds for Non-Deterministic Time | 2023-03-02 | Paper |
| A parameterized halting problem, $\Delta_0$ truth and the MRDP theorem | 2022-11-11 | Paper |
On representations of intended structures in foundational theories
Journal of Philosophical Logic | 2022-04-04 | Paper |
Typical forcings, NP search problems and an extension of a theorem of Riis
Annals of Pure and Applied Logic | 2021-03-25 | Paper |
A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science | 2021-01-20 | Paper |
Cobham recursive set functions and weak set theories
Sets and Computations | 2020-12-02 | Paper |
Automating resolution is NP-hard
Journal of the ACM | 2020-11-11 | Paper |
Automating resolution is NP-hard
Journal of the ACM | 2020-11-11 | Paper |
A remark on pseudo proof systems and hard instances of the satisfiability problem
Mathematical Logic Quarterly | 2020-05-11 | Paper |
Polynomial time ultrapowers and the consistency of circuit lower bounds
Archive for Mathematical Logic | 2020-01-17 | Paper |
The parameterized space complexity of model-checking bounded variable first-order logic
(available as arXiv preprint) | 2019-11-26 | Paper |
Feasibly constructive proofs of succinct weak circuit lower bounds
Annals of Pure and Applied Logic | 2019-11-22 | Paper |
Feasible set functions have small circuits
Computability | 2019-10-28 | Paper |
One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | 2018-04-23 | Paper |
One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
ACM Transactions on Computational Logic | 2018-03-22 | Paper |
The parameterized space complexity of embedding along a path
Theory of Computing Systems | 2017-10-12 | Paper |
The treewidth of proofs
Information and Computation | 2017-08-08 | Paper |
An algebraic preservation theorem for aleph-zero categorical quantified constraint satisfaction
2012 27th Annual IEEE Symposium on Logic in Computer Science | 2017-05-16 | Paper |
The fine classification of conjunctive queries and parameterized logarithmic space
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
The fine classification of conjunctive queries and parameterized logarithmic space
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Cobham recursive set functions
Annals of Pure and Applied Logic | 2016-01-12 | Paper |
Hard instances of algorithms and proof systems
ACM Transactions on Computation Theory | 2015-09-03 | Paper |
Consistency, optimality, and incompleteness
Annals of Pure and Applied Logic | 2015-08-27 | Paper |
Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
Journal of Symbolic Logic | 2015-08-14 | Paper |
Topological dynamics of unordered Ramsey structures
Fundamenta Mathematicae | 2015-03-26 | Paper |
Partially definable forcing and bounded arithmetic
Archive for Mathematical Logic | 2015-02-23 | Paper |
Bounded variable logic, parameterized logarithmic space, and Savitch's theorem
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Revisiting space in proof complexity: treewidth and pathwidth
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Parameterized random complexity
Theory of Computing Systems | 2013-04-15 | Paper |
An algebraic preservation theorem for \(\aleph_0\)-categorical quantified constraint satisfaction
Logical Methods in Computer Science | 2013-04-09 | Paper |
Some definitorial suggestions for parameterized proof complexity
Parameterized and Exact Computation | 2013-01-07 | Paper |
Hard instances of algorithms and proof systems
Lecture Notes in Computer Science | 2012-08-14 | Paper |
Strong isomorphism reductions in complexity theory
Journal of Symbolic Logic | 2011-12-23 | Paper |
Consistency and optimality
Models of Computation in Context | 2011-09-09 | Paper |
Lower bounds for kernelizations and other preprocessing procedures
Theory of Computing Systems | 2011-05-25 | Paper |
Lower bounds for kernelizations and other preprocessing procedures
Mathematical Theory and Computational Practice | 2010-07-28 | Paper |
W-hierarchies defined by symmetric gates
Theory of Computing Systems | 2010-05-10 | Paper |
| scientific article; zbMATH DE number 5529641 (Why is no real title available?) | 2009-03-17 | Paper |
Parameterized Derandomization
Parameterized and Exact Computation | 2008-06-05 | Paper |
A Purely Democratic Characterization of W[1]
Parameterized and Exact Computation | 2008-06-05 | Paper |
Randomized Approximations of Parameterized Counting Problems
Parameterized and Exact Computation | 2008-06-03 | Paper |
