| Publication | Date of Publication | Type |
|---|
| Proving unsatisfiability with hitting formulas | 2025-11-04 | Paper |
Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
SIAM Journal on Computing | 2024-06-27 | Paper |
Irreducible subcube partitions
The Electronic Journal of Combinatorics | 2024-02-23 | Paper |
Gregory Samuilovich Tseytin (obituary)
Russian Mathematical Surveys | 2024-01-25 | Paper |
Improving \(3N\) circuit complexity lower bounds
Computational Complexity | 2024-01-24 | Paper |
The power of the binary value principle
Lecture Notes in Computer Science | 2023-10-04 | Paper |
| Proving Unsatisfiability with Hitting Formulas | 2023-02-13 | Paper |
Local search algorithms for SAT: Worst-case analysis
Algorithm Theory — SWAT'98 | 2022-12-09 | Paper |
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
On the limits of gate elimination
Journal of Computer and System Sciences | 2018-06-06 | Paper |
| On the limits of gate elimination | 2018-03-21 | Paper |
On the probabilistic closure of the loose unambiguous hierarchy
Information Processing Letters | 2015-06-02 | Paper |
Obituary: Nikolai Aleksandrovich Shanin (1919--2011)
Russian Mathematical Surveys | 2013-12-17 | Paper |
Optimal heuristic algorithms for the image of an injective function
Journal of Mathematical Sciences (New York) | 2013-04-09 | Paper |
Feebly secure cryptographic primitives
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 |
Satisfiability certificates verifiable in subexponential time
Theory and Applications of Satisfiability Testing - SAT 2011 | 2011-06-17 | Paper |
An infinitely-often one-way function based on an average-case assumption
St. Petersburg Mathematical Journal | 2010-09-01 | Paper |
Optimal acceptors and optimal proof systems
Lecture Notes in Computer Science | 2010-06-17 | Paper |
Time hierarchies for cryptographic function inversion with advice
Journal of Mathematical Sciences (New York) | 2010-01-15 | Paper |
| Complexity of semialgebraic proofs with restricted degree of falsity | 2009-10-12 | Paper |
A Feebly Secure Trapdoor Function
Computer Science - Theory and Applications | 2009-08-18 | Paper |
A Complete Public-Key Cryptosystem
Groups - Complexity - Cryptology | 2009-03-23 | Paper |
An Infinitely-Often One-Way Function Based on an Average-Case Assumption
Logic, Language, Information and Computation | 2008-07-10 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
Lecture Notes in Computer Science | 2007-05-02 | Paper |
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Journal of Automated Reasoning | 2007-01-24 | Paper |
Several notes on the power of Gomory-Chvátal cuts
Annals of Pure and Applied Logic | 2006-08-16 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2005-12-15 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Algorithms for Sat and upper bounds on their complexity
Journal of Mathematical Sciences (New York) | 2005-08-05 | Paper |
UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
Annals of Mathematics and Artificial Intelligence | 2005-05-13 | Paper |
| scientific article; zbMATH DE number 2086404 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2086627 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2084740 (Why is no real title available?) | 2004-08-09 | Paper |
| scientific article; zbMATH DE number 1916823 (Why is no real title available?) | 2004-01-14 | Paper |
Worst-case study of local search for MAX-\(k\)-SAT.
Discrete Applied Mathematics | 2003-09-15 | Paper |
Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Discrete Applied Mathematics | 2003-09-15 | Paper |
Algebraic proof systems over formulas.
Theoretical Computer Science | 2003-08-17 | Paper |
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
Theoretical Computer Science | 2003-01-21 | Paper |
MAX SAT approximation beyond the limits of polynomial-time approximation
Annals of Pure and Applied Logic | 2002-03-13 | Paper |
| scientific article; zbMATH DE number 1670827 (Why is no real title available?) | 2001-11-11 | Paper |
| New worst-case upper bounds for SAT | 2001-10-21 | Paper |
| SAT local search algorithms: Worst-case study | 2001-10-21 | Paper |
SAT local search algorithms: Worst-case study
Journal of Automated Reasoning | 2001-09-03 | Paper |
New worst-case upper bounds for SAT
Journal of Automated Reasoning | 2001-05-14 | Paper |
| scientific article; zbMATH DE number 1500507 (Why is no real title available?) | 2001-05-06 | Paper |
| scientific article; zbMATH DE number 1303594 (Why is no real title available?) | 2000-05-18 | Paper |
On construction of a symbolic realization of hyperbolic automorphisms of the torus
Journal of Mathematical Sciences (New York) | 1998-06-08 | Paper |
A fast deterministic algorithm for formulas that have many satisfying assignments
Logic Journal of the IGPL | 1998-03-17 | Paper |
