Edward A. Hirsch

90 papers A* 6A 10B 1C 4Misc 5Journal 58Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A conf
Upper and Lower Bounds for the Linear Ordering Principle.
STACS
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
A Note on Avoid vs MCSP.
CoRR
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
A Note on Avoid vs MCSP.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
The power of the Binary Value Principle.
Ann. Pure Appl. Log.
Yaroslav Alekseev, Edward A. Hirsch
2025 A conf
Tropical Proof Systems: Between R(CP) and Resolution.
STACS
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch
2025 J jnl
Upper and Lower Bounds for the Linear Ordering Principle.
CoRR
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
Upper and Lower Bounds for the Linear Ordering Principle.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Ilya Volkovich
2024 A conf
Proving Unsatisfiability with Hitting Formulas.
ITCS
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2024 J jnl
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?
SIAM J. Comput.
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
2024 J jnl
Tropical proof systems.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch
2023 J jnl
Improving 3N Circuit Complexity Lower Bounds.
Comput. Complex.
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2023 J jnl
Irreducible Subcube Partitions.
Electron. J. Comb.
Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Ryazanov, Alexander V. Smal, Marc Vinyals
2023 J jnl
Proving Unsatisfiability with Hitting Formulas.
CoRR
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2023 J jnl
Proving Unsatisfiability with Hitting Formulas.
Electron. Colloquium Comput. Complex.
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2023 C conf
The Power of the Binary Value Principle.
CIAC
Yaroslav Alekseev, Edward A. Hirsch
2022 J jnl
Irreducible subcube partitions.
CoRR
Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals
2022 J jnl
The power of the Binary Value Principle.
CoRR
Yaroslav Alekseev, Edward A. Hirsch
2022 J jnl
The power of the Binary Value Principle.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Edward A. Hirsch
2021 — ch.
Worst-Case Upper Bounds.
Handbook of Satisfiability
Evgeny Dantsin, Edward A. Hirsch
2020 A* conf
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
STOC
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
2019 J jnl
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
2019 J jnl
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture: Can a Natural Number be Negative?
CoRR
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
2018 J jnl
On the limits of gate elimination.
J. Comput. Syst. Sci.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2017 J jnl
Preface.
Theory Comput. Syst.
Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin
2016 A* conf
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function.
FOCS
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2016 — ch.
Exact Algorithms for General CNF SAT.
Encyclopedia of Algorithms
Edward A. Hirsch
2016 B conf
On the Limits of Gate Elimination.
MFCS
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2016 J jnl
On the Limits of Gate Elimination.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2015 J jnl
A better-than-3n lower bound for the circuit complexity of an explicit function.
Electron. Colloquium Comput. Complex.
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2015 J jnl
On the probabilistic closure of the loose unambiguous hierarchy.
Inf. Process. Lett.
Edward A. Hirsch, Dmitry Sokolov
2015 J jnl
Preface.
Theory Comput. Syst.
Juhani Karhumäki, Edward A. Hirsch
2015 J jnl
Russian Chapter of European Association for Theoretical Computer Science.
Bull. EATCS
Edward A. Hirsch
2014 Misc ed.
Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings
CSR
Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Éric Pin, Nikolay K. Vereshchagin
2014 J jnl
On the probabilistic closure of the loose unambiguous hierarchy.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Sokolov
2014 J jnl
Optimal algorithms and proofs (Dagstuhl Seminar 14421).
Dagstuhl Reports
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam
2012 Misc ed.
Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings
CSR
Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö, Michail Kh. Prilutskii
2012 J jnl
On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography.
Theory Comput. Syst.
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
2012 J jnl
On an optimal randomized acceptor for graph nonisomorphism.
Inf. Process. Lett.
Edward A. Hirsch, Dmitry Itsykson
2011 J jnl
Optimal heuristic algorithms for the image of an injective function.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal
2011 A conf
Satisfiability Certificates Verifiable in Subexponential Time.
SAT
Evgeny Dantsin, Edward A. Hirsch
2010 A conf
On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity.
STACS
Edward A. Hirsch, Dmitry Itsykson
2010 J jnl
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
2010 C conf
Optimal Acceptors and Optimal Proof Systems.
TAMC
Edward A. Hirsch
2009 J jnl
A Complete Public-Key Cryptosystem.
Groups Complex. Cryptol.
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev
2009 Misc conf
A Feebly Secure Trapdoor Function.
CSR
Edward A. Hirsch, Sergey I. Nikolenko
2009 J jnl
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.
J. Satisf. Boolean Model. Comput.
Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko
2009 J jnl
On optimal heuristic randomized semidecision procedures, with application to proof complexity
CoRR
Edward A. Hirsch, Dmitry Itsykson
2009 — ch.
Worst-Case Upper Bounds.
Handbook of Satisfiability
Evgeny Dantsin, Edward A. Hirsch
2008 C conf
An Infinitely-Often One-Way Function Based on an Average-Case Assumption.
WoLLIC
Edward A. Hirsch, Dmitry Itsykson
2008 Misc ed.
Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings
CSR
Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, Anatol Slissenko
2008 — ch.
Exact Algorithms for General CNF SAT.
Encyclopedia of Algorithms
Edward A. Hirsch
2007 J jnl
An infinitely-often one-way function based on an average-case assumption.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson
2006 J jnl
A Complete Public-Key Cryptosystem.
Electron. Colloquium Comput. Complex.
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev
2006 C conf
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms.
CIAC
Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert
2006 Misc ed.
Computer Science - Theory and Applications, First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings
CSR
Dima Grigoriev, John Harrison, Edward A. Hirsch
2006 J jnl
Several notes on the power of Gomory-Chvátal cuts.
Ann. Pure Appl. Log.
Edward A. Hirsch, Arist Kojevnikov
2005 J jnl
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
Electron. Colloquium Comput. Complex.
Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert
2005 J jnl
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.
J. Autom. Reason.
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2005 A conf
Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution.
SAT
Edward A. Hirsch, Sergey I. Nikolenko
2005 J jnl
Simulating Cutting Plane proofs with restricted degree of falsity by Resolution
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Sergey I. Nikolenko
2005 J jnl
The SAT2002 competition.
Ann. Math. Artif. Intell.
Laurent Simon, Daniel Le Berre, Edward A. Hirsch
2005 J jnl
Time hierarchies for cryptographic function inversion with advice
Electron. Colloquium Comput. Complex.
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev
2005 J jnl
UnitWalk: A new SAT solver that uses local search guided by unit clause elimination.
Ann. Math. Artif. Intell.
Edward A. Hirsch, Arist Kojevnikov
2004 A conf
Algorithms for SAT Based on Search in Hamming Balls.
STACS
Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert
2004 A* conf
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.
ICALP
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2004 J jnl
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2003 J jnl
Algebraic proof systems over formulas.
Theor. Comput. Sci.
Dima Grigoriev, Edward A. Hirsch
2003 J jnl
Algorithms for SAT based on search in Hamming balls
Electron. Colloquium Comput. Complex.
Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert
2003 J jnl
Several notes on the power of Gomory-Chvatal cuts
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Arist Kojevnikov
2003 J jnl
Worst-case study of local search for MAX-k-SAT.
Discret. Appl. Math.
Edward A. Hirsch
2003 J jnl
Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Discret. Appl. Math.
Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith
2002 J jnl
A deterministic (2-2/(k+1))
Theor. Comput. Sci.
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning
2002 A conf
Complexity of Semi-algebraic Proofs.
STACS
Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
2002 A* conf
Exponential Lower Bound for Static Semi-algebraic Proofs.
ICALP
Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
2001 J jnl
Algebraic proof systems over formulas
Electron. Colloquium Comput. Complex.
Dima Grigoriev, Edward A. Hirsch
2001 J jnl
Algorithms for SAT and Upper Bounds on Their Complexity
Electron. Colloquium Comput. Complex.
Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, Maxim Vsemirnov
2001 J jnl
Complexity of semi-algebraic proofs
Electron. Colloquium Comput. Complex.
Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
2001 J jnl
MAX SAT approximation beyond the limits of polynomial-time approximation.
Ann. Pure Appl. Log.
Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev
2001 A conf
Solving Boolean Satisfiability Using Local Search Guided by Unit Clause Elimination.
CP
Edward A. Hirsch, Arist Kojevnikov
2000 A conf
A New Algorithm for MAX-2-SAT.
STACS
Edward A. Hirsch
2000 A* conf
Deterministic Algorithms for
ICALP
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning
2000 J jnl
New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT
Electron. Colloquium Comput. Complex.
Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith
2000 J jnl
New Worst-Case Upper Bounds for SAT.
J. Autom. Reason.
Edward A. Hirsch
2000 J jnl
SAT Local Search Algorithms: Worst-Case Study.
J. Autom. Reason.
Edward A. Hirsch
2000 — conf
Worst-case Time Bounds for MAX-k-SAT with respect to the Number of Variables Using Local Search.
ICALP Satellite Workshops
Edward A. Hirsch
2000 J jnl
Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search
Electron. Colloquium Comput. Complex.
Edward A. Hirsch
1999 J jnl
A New Algorithm for MAX-2-SAT
Electron. Colloquium Comput. Complex.
Edward A. Hirsch
1998 J jnl
A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments.
Log. J. IGPL
Edward A. Hirsch
1998 — conf
Local Search Algorithms for SAT: Worst-Case Analysis.
SWAT
Edward A. Hirsch
1998 A* conf
Two New Upper Bounds for SAT.
SODA
Edward A. Hirsch