Edward A. Hirsch: Research papers and surveys
-
For every part of my research, only the last version is provided (subsuming previous
publications, if any).
-
The pdf's on this page are drafts (as updated as possible).
In a few cases of very copyrighted material, a link to the publisher's page is provided instead.
- Proving Unsatisfiability with Hitting Formulas (with Y.Filmus, A.Riazanov, A.Smal, M.Vinyals).
- Irreducible subcube partitions (with Y.Filmus, S.Kurz, F.Ihringer, A.Riazanov, A.Smal, M.Vinyals).
- The power of the Binary Value Principle (with Y.Alekseev).
- Semi-algebraic proofs, IPS lower bounds and the τ-conjecture: can a natural number be negative? (with Y.Alekseev, D.Grigoriev, I.Tzameret).
- On the limits of gate elimination (with A.Golovnev, A.Knop, A.Kulikov).
-
Improving 3n circuit complexity lower bounds (with M.G.Find, A.Golovnev, A.Kulikov).
-
On the probabilistic closure of the loose unambiguous hierarchy (with D.Sokolov).
-
Succinct interactive proofs for quantified boolean formulas (with D.van Melkebeek, A.Smal).
-
On an optimal randomized acceptor for graph nonisomorphism (with D.Itsykson).
-
Optimal heuristic algorithms for the image of an injective function
(with D.Itsykson, V.Nikolaenko, A.Smal).
-
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography (with D.Itsykson, I.Monakhov, A.Smal).
-
Optimal acceptors and optimal proof systems.
-
Feebly secure cryptographic primitives (with O.Melanich, S.I.Nikolenko).
-
Satisfiability certificates verifiable in subexponential time (with E.Dantsin).
-
Complexity of semialgebraic proofs with restricted degree of falsity
(with A.Kojevnikov, A.S.Kulikov, S.I.Nikolenko).
-
[2021 edition!] Worst-case upper bounds (with E.Dantsin) [links from publisher: 1, 2].
-
Exact algorithms for general CNF SAT.
-
An infinitely-often one-way function based on an average-case assumption
(with D.Itsykson).
-
A complete public-key cryptosystem (with D.Grigoriev, K.Pervyshev).
-
Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms
(with E.Dantsin, A.Wolpert)
-
Time hierarchies for cryptographic function inversion with advice
(with D.Grigoriev, K.Pervyshev).
-
Exponential lower bounds for the running time of DPLL algorithms on
satisfiable formulas
(with M.Alekhnovich, D.Itsykson).
-
Algorithms for SAT based on search in Hamming balls
(with E.Dantsin, A.Wolpert).
-
Several notes on the power of Gomory-Chvátal cuts
(with A.Kojevnikov).
-
Complexity of semialgebraic proofs
(with D.Grigoriev, D.Pasechnik).
-
UnitWalk: A new SAT solver
that uses local search guided by
unit clause elimination
(with A.Kojevnikov).
-
The SAT2002 Competition
(with L.Simon, D.Le Berre).
-
Algebraic proof systems over formulas
(with D.Grigoriev).
-
Algorithms for SAT and upper bounds on their complexity
(with E.Dantsin, S.Ivanov, M.Vsemirnov).
-
A Deterministic (2-2/(k+1))^n
Algorithm for k-SAT Based on Local Search
(with E.Dantsin,
A.Goerdt,
R.Kannan,
J.Kleinberg,
C.Papadimitriou,
P.Raghavan,
U.Schöning).
-
Worst-case study of local search for
MAX-k-SAT.
-
New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT
(with J.Gramm, R.Niedermeier, P.Rossmanith).
-
SAT local search algorithms: worst-case study.
-
New worst-case upper bounds for SAT.
-
MAX SAT approximation beyond the limits of
polynomial-time approximation
(with E.Dantsin,
M.R.Gavrilovich,
B.Konev).
-
Separating sings in the propositional
satisfiability problem.
-
A fast deterministic algorithm for formulas that have
many satisfying assignments.
-
On symbolic realization of
hyperbolic automorphisms of torus.
-
Picture (array) grammars and plane automata.
Please contact me if you have questions,
comments, or problems with getting these papers.