| Publication | Date of Publication | Type |
|---|
| Automating OBDD proofs is NP-hard | 2024-08-06 | Paper |
| Tight bounds for tseitin formulas | 2024-07-12 | Paper |
| Proof complexity of natural formulas via communication arguments | 2023-07-12 | Paper |
Lower Bounds on OBDD Proofs with Several Orders
ACM Transactions on Computational Logic | 2022-12-08 | Paper |
Bounded-depth Frege complexity of Tseitin formulas for all graphs
Annals of Pure and Applied Logic | 2022-10-14 | Paper |
| Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs | 2022-07-21 | Paper |
Computational and proof complexity of partial string avoidability
ACM Transactions on Computation Theory | 2022-03-14 | Paper |
Correction to: ``Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
Computational Complexity | 2022-01-03 | Paper |
Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
Computational Complexity | 2021-09-10 | Paper |
On Tseitin formulas, read-once branching programs and treewidth
Theory of Computing Systems | 2021-08-03 | Paper |
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
Journal of Symbolic Logic | 2021-01-29 | Paper |
| scientific article; zbMATH DE number 7250156 (Why is no real title available?) | 2020-09-22 | Paper |
| Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs | 2020-05-26 | Paper |
Resolution over linear equations modulo two
Annals of Pure and Applied Logic | 2019-11-06 | Paper |
| On Tseitin formulas, read-once branching programs and treewidth | 2019-10-22 | Paper |
| On OBDD-based algorithms and proof systems that dynamically change order of variables | 2018-04-19 | Paper |
| Complexity of distributions and average-case hardness | 2018-04-19 | Paper |
| scientific article; zbMATH DE number 6851884 (Why is no real title available?) | 2018-03-21 | Paper |
| Hard satisfiable formulas for splittings by linear combinations | 2017-11-15 | Paper |
Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
Theory of Computing Systems | 2017-11-07 | Paper |
Tight lower bounds on the resolution complexity of perfect matching principles
Fundamenta Informaticae | 2017-07-28 | Paper |
Heuristic time hierarchies via hierarchies for sampling distributions
Algorithms and Computation | 2016-01-11 | Paper |
Resolution complexity of perfect matching principles for sparse graphs
Lecture Notes in Computer Science | 2015-10-20 | Paper |
On fast heuristic non-deterministic algorithms and short heuristic proofs
Fundamenta Informaticae | 2014-12-22 | Paper |
Lower Bounds for Splittings by Linear Combinations
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Graph expansion, Tseitin formulas and resolution proofs for CSP
Computer Science – Theory and Applications | 2013-06-14 | Paper |
Optimal heuristic algorithms for the image of an injective function
Journal of Mathematical Sciences (New York) | 2013-04-09 | Paper |
The complexity of inverting explicit Goldreich's function by DPLL algorithms
Journal of Mathematical Sciences (New York) | 2013-04-09 | Paper |
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
Theory of Computing Systems | 2012-12-07 | Paper |
On an optimal randomized acceptor for graph nonisomorphism
Information Processing Letters | 2012-05-04 | Paper |
| scientific article; zbMATH DE number 5999718 (Why is no real title available?) | 2012-01-23 | Paper |
Lower bounds for myopic DPLL algorithms with a cut heuristic
Algorithms and Computation | 2011-12-16 | Paper |
Structural complexity of AvgBPP
Annals of Pure and Applied Logic | 2011-09-12 | Paper |
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
Computer Science – Theory and Applications | 2011-06-17 | Paper |
An infinitely-often one-way function based on an average-case assumption
St. Petersburg Mathematical Journal | 2010-09-01 | Paper |
Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
Computer Science – Theory and Applications | 2010-06-22 | Paper |
Structural Complexity of AvgBPP
Computer Science - Theory and Applications | 2009-08-18 | Paper |
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
Automata, Languages and Programming | 2009-03-12 | Paper |
An Infinitely-Often One-Way Function Based on an Average-Case Assumption
Logic, Language, Information and Computation | 2008-07-10 | Paper |
| scientific article; zbMATH DE number 5161489 (Why is no real title available?) | 2007-06-04 | Paper |
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Journal of Automated Reasoning | 2007-01-24 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
