| Publication | Date of Publication | Type |
|---|
| Hard QBFs for merge resolution | 2026-03-23 | Paper |
| New lower bounds for polynomial calculus over non-Boolean bases | 2026-02-03 | Paper |
Pseudo-deterministic query complexity of search problems
Computational Complexity | 2025-11-28 | Paper |
Runtime vs. extracted proof size: an exponential gap for CDCL on QBFs
Journal of Automated Reasoning | 2025-11-26 | Paper |
| Dependency schemes in CDCL-based QBF solving: a proof-theoretic study | 2025-07-28 | Paper |
Hard QBFs for merge resolution
ACM Transactions on Computation Theory | 2025-02-25 | Paper |
| Query complexity of search problems | 2024-12-03 | Paper |
QBF merge resolution is powerful but unnatural
Logical Methods in Computer Science | 2024-11-12 | Paper |
Dependency schemes in CDCL-based QBF solving: a proof-theoretic study
Journal of Automated Reasoning | 2024-09-27 | Paper |
| QBF merge resolution is powerful but unnatural | 2024-07-12 | Paper |
| scientific article; zbMATH DE number 7799593 (Why is no real title available?) | 2024-02-05 | Paper |
On (simple) decision tree rank
Theoretical Computer Science | 2023-10-12 | Paper |
Linear threshold functions in decision lists, decision trees, and depth-2 circuits
Information Processing Letters | 2023-10-12 | Paper |
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
ACM Transactions on Computational Logic | 2023-04-05 | Paper |
| Logspace verifiers, NC, and NP | 2023-03-21 | Paper |
MaxSAT Resolution and Subcube Sums
ACM Transactions on Computational Logic | 2023-02-07 | Paper |
Determinant: Old algorithms, new insights
Algorithm Theory — SWAT'98 | 2022-12-09 | Paper |
scientific article; zbMATH DE number 7561749 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7559123 (Why is no real title available?) | 2022-07-18 | Paper |
Building strategies into QBF proofs
Journal of Automated Reasoning | 2021-06-09 | Paper |
Lower bounds for linear decision lists
Chicago Journal of Theoretical Computer Science | 2021-05-14 | Paper |
MaxSAT resolution and subcube sums
(available as arXiv preprint) | 2021-04-07 | Paper |
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science | 2021-01-21 | Paper |
| Lower bound techniques for QBF proof systems | 2020-08-05 | Paper |
| scientific article; zbMATH DE number 7204408 (Why is no real title available?) | 2020-05-26 | Paper |
| Short proofs in QBF expansion | 2020-05-20 | Paper |
Space-efficient approximations for subset sum
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Small depth proof systems
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
| A quest for structure in complexity | 2019-07-03 | Paper |
Understanding cutting planes for QBFs
Information and Computation | 2018-09-27 | Paper |
Some complete and intermediate polynomials in algebraic complexity theory
Theory of Computing Systems | 2018-06-01 | Paper |
| Understanding cutting planes for QBFs | 2018-04-19 | Paper |
Are Short Proofs Narrow? QBF Resolution Is <i>Not</i> So Simple
ACM Transactions on Computational Logic | 2018-03-22 | Paper |
| Are Short Proofs Narrow? QBF Resolution is not Simple. | 2018-01-24 | Paper |
Sums of read-once formulas: how many summands are necessary?
Theoretical Computer Science | 2017-12-20 | Paper |
The shifted partial derivative complexity of elementary symmetric polynomials
Theory of Computing | 2017-10-11 | Paper |
| Feasible interpolation for QBF resolution calculi | 2017-06-22 | Paper |
| Homomorphism polynomials complete for VP | 2017-04-25 | Paper |
Building above read-once polynomials: identity testing and hardness of representation
Algorithmica | 2016-12-21 | Paper |
Algebraic complexity classes
Perspectives in Computational Complexity | 2016-09-22 | Paper |
Sums of read-once formulas: how many summands suffice?
Computer Science – Theory and Applications | 2016-07-25 | Paper |
Some complete and intermediate polynomials in algebraic complexity theory
Lecture Notes in Computer Science | 2016-07-25 | Paper |
Homomorphism polynomials complete for VP
Chicago Journal of Theoretical Computer Science | 2016-05-24 | Paper |
Level-ordered \(Q\)-resolution and tree-like \(Q\)-resolution are incomparable
Information Processing Letters | 2016-01-05 | Paper |
\textsf{VNP} = \textsf{VP} in the multilinear world
Information Processing Letters | 2015-12-01 | Paper |
Feasible interpolation for QBF resolution calculi
Automata, Languages, and Programming | 2015-10-27 | Paper |
Planarity, determinants, permanents, and (unique) matchings
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
| scientific article; zbMATH DE number 6472651 (Why is no real title available?) | 2015-08-14 | Paper |
A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Building above read-once polynomials: identity testing and hardness of representation
Lecture Notes in Computer Science | 2014-09-26 | Paper |
Longest paths in planar DAGs in unambiguous log-space
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Some perfect matchings and perfect half-integral matchings in NC
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Monomials, multilinearity and identity testing in simple read-restricted circuits
Theoretical Computer Science | 2014-02-11 | Paper |
Comments on ``Arithmetic complexity, Kleene closure, and formal power series''
Theory of Computing Systems | 2013-10-21 | Paper |
Resource trade-offs in syntactically multilinear arithmetic circuits
Computational Complexity | 2013-09-30 | Paper |
Small depth proof systems
Lecture Notes in Computer Science | 2013-09-20 | Paper |
Small space analogues of Valiant's classes and the limitations of skew formulas
Computational Complexity | 2013-04-11 | Paper |
Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
Algorithmica | 2012-11-21 | Paper |
Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs
Mathematical Foundations of Computer Science 2012 | 2012-09-25 | Paper |
The complexity of unary subset sum
Lecture Notes in Computer Science | 2012-09-25 | Paper |
The planar \(k\)-means problem is NP-hard
Theoretical Computer Science | 2012-08-08 | Paper |
Upper bounds for monotone planar circuit value and variants
Computational Complexity | 2011-02-18 | Paper |
| On the complexity of membership and counting in height-deterministic pushdown automata | 2010-09-20 | Paper |
Counting paths in VPA is complete for \#NC\(^{1}\)
Lecture Notes in Computer Science | 2010-07-20 | Paper |
Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
Theory of Computing Systems | 2010-05-05 | Paper |
Rigidity of a simple extended lower triangular matrix
Information Processing Letters | 2010-04-19 | Paper |
On the complexity of matrix rank and rigidity
Theory of Computing Systems | 2010-03-05 | Paper |
Small-Space Analogues of Valiant’s Classes
Fundamentals of Computation Theory | 2009-10-20 | Paper |
| scientific article; zbMATH DE number 5605106 (Why is no real title available?) | 2009-09-19 | Paper |
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
Language and Automata Theory and Applications | 2009-04-02 | Paper |
On the Bipartite Unique Perfect Matching Problem
Automata, Languages and Programming | 2009-03-12 | Paper |
Parameterizing above or below guaranteed values
Journal of Computer and System Sciences | 2009-03-11 | Paper |
The Planar k-Means Problem is NP-Hard
WALCOM: Algorithms and Computation | 2009-02-24 | Paper |
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
Lecture Notes in Computer Science | 2009-02-03 | Paper |
Simultaneous matchings: Hardness and approximation
Journal of Computer and System Sciences | 2008-06-26 | Paper |
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
Computer Science – Theory and Applications | 2008-06-05 | Paper |
On the Complexity of Matrix Rank and Rigidity
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Planarity, Determinants, Permanents, and (Unique) Matchings
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Parameterizing MAX SNP Problems Above Guaranteed Values
Parameterized and Exact Computation | 2008-06-03 | Paper |
Evaluating Monotone Circuits on Cylinders, Planes and Tori
STACS 2006 | 2008-03-19 | Paper |
Arithmetizing Classes Around NC 1 and L
STACS 2007 | 2007-09-03 | Paper |
On Sorting by 3-Bounded Transpositions
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
APPROXIMATE BLOCK SORTING
International Journal of Foundations of Computer Science | 2006-05-10 | Paper |
Algorithms – ESA 2004
Lecture Notes in Computer Science | 2005-08-18 | Paper |
The combinatorial approach yields an NC algorithm for computing Pfaffians
Discrete Applied Mathematics | 2004-11-23 | Paper |
The complexity of planarity testing
Information and Computation | 2004-11-23 | Paper |
| scientific article; zbMATH DE number 2077109 (Why is no real title available?) | 2004-07-01 | Paper |
Arithmetic complexity, Kleene closure, and formal power series
Theory of Computing Systems | 2003-08-26 | Paper |
| scientific article; zbMATH DE number 1500509 (Why is no real title available?) | 2001-04-26 | Paper |
| scientific article; zbMATH DE number 1405680 (Why is no real title available?) | 2000-10-18 | Paper |
Determinant: Old Algorithms, New Insights
SIAM Journal on Discrete Mathematics | 1999-11-23 | Paper |
Parameterizing above Guaranteed Values: MaxSat and MaxCut
Journal of Algorithms | 1999-09-29 | Paper |
| scientific article; zbMATH DE number 1332669 (Why is no real title available?) | 1999-09-08 | Paper |
| scientific article; zbMATH DE number 1300963 (Why is no real title available?) | 1999-06-16 | Paper |
Non-commutative arithmetic circuits: depth reduction and size lower bounds
Theoretical Computer Science | 1999-01-12 | Paper |
A note on Mod and generalised Mod classes
Information Processing Letters | 1997-02-28 | Paper |
Nondeterministic, probabilistic and alternating computations on cellular array models
Theoretical Computer Science | 1997-02-28 | Paper |
A note on SpanP functions
Information Processing Letters | 1994-08-03 | Paper |
Language classes defined by time-bounded relativised cellular automata
RAIRO - Theoretical Informatics and Applications | 1994-04-19 | Paper |
| scientific article; zbMATH DE number 176948 (Why is no real title available?) | 1993-05-18 | Paper |
Some results on time-varying and relativised cellular automata<sup>*</sup>
International Journal of Computer Mathematics | 1993-01-16 | Paper |
Fuzzy L-systems
International Journal of Computer Mathematics | 1990-01-01 | Paper |
