Edward A. Hirsch

According to our database, Edward A. Hirsch authored at least 59 papers between 1998 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Upper and Lower Bounds for the Linear Ordering Principle.

Edward A. Hirsch, Ilya Volkovich

CoRR, March, 2025

Tropical Proof Systems: Between R(CP) and Resolution.

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

SIAM J. Comput., 2024

Tropical proof systems.

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch

Electron. Colloquium Comput. Complex., 2024

Proving Unsatisfiability with Hitting Formulas.

Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Improving 3N Circuit Complexity Lower Bounds.

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

Comput. Complex., December, 2023

Irreducible Subcube Partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Ryazanov, Alexander V. Smal, Marc Vinyals

Electron. J. Comb., 2023

The Power of the Binary Value Principle.

Yaroslav Alekseev, Edward A. Hirsch

Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

2022

Irreducible subcube partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals

CoRR, 2022

2021

Worst-Case Upper Bounds.

Evgeny Dantsin, Edward A. Hirsch

Proceedings of the Handbook of Satisfiability - Second Edition, 2021

2020

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2019

2017

Preface.

Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin

Theory Comput. Syst., 2017

2016

Exact Algorithms for General CNF SAT.

Edward A. Hirsch

Encyclopedia of Algorithms, 2016

On the Limits of Gate Elimination.

Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function.

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Preface.

Juhani Karhumäki, Edward A. Hirsch

Theory Comput. Syst., 2015

Russian Chapter of European Association for Theoretical Computer Science.

Edward A. Hirsch

Bull. EATCS, 2015

2014

On the probabilistic closure of the loose unambiguous hierarchy.

Edward A. Hirsch, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2014

Optimal algorithms and proofs (Dagstuhl Seminar 14421).

Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam

Dagstuhl Reports, 2014

2012

On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography.

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

Theory Comput. Syst., 2012

On an optimal randomized acceptor for graph nonisomorphism.

Edward A. Hirsch, Dmitry Itsykson

Inf. Process. Lett., 2012

2011

Optimal heuristic algorithms for the image of an injective function.

Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Electron. Colloquium Comput. Complex., 2011

Satisfiability Certificates Verifiable in Subexponential Time.

Evgeny Dantsin, Edward A. Hirsch

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2011, 2011

2010

Optimal Acceptors and Optimal Proof Systems.

Edward A. Hirsch

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity.

Edward A. Hirsch, Dmitry Itsykson

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Worst-Case Upper Bounds.

Evgeny Dantsin, Edward A. Hirsch

Proceedings of the Handbook of Satisfiability, 2009

Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.

Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko

J. Satisf. Boolean Model. Comput., 2009

A Feebly Secure Trapdoor Function.

Edward A. Hirsch, Sergey I. Nikolenko

Proceedings of the Computer Science, 2009

2008

Exact Algorithms for General CNF SAT.

Edward A. Hirsch

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

An Infinitely-Often One-Way Function Based on an Average-Case Assumption.

Edward A. Hirsch, Dmitry Itsykson

Proceedings of the Logic, 2008

2006

A Complete Public-Key Cryptosystem.

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2006

Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms.

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005

Time hierarchies for cryptographic function inversion with advice

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2005

The SAT2002 competition.

Laurent Simon, Daniel Le Berre, Edward A. Hirsch

Ann. Math. Artif. Intell., 2005

UnitWalk: A new SAT solver that uses local search guided by unit clause elimination.

Edward A. Hirsch, Arist Kojevnikov

Ann. Math. Artif. Intell., 2005

Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution.

Edward A. Hirsch, Sergey I. Nikolenko

Proceedings of the Theory and Applications of Satisfiability Testing, 2005

2004

Algorithms for SAT Based on Search in Hamming Balls.

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Proceedings of the STACS 2004, 2004

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Several notes on the power of Gomory-Chvatal cuts

Edward A. Hirsch, Arist Kojevnikov

Electron. Colloquium Comput. Complex., 2003

Worst-case study of local search for MAX-k-SAT.

Edward A. Hirsch

Discret. Appl. Math., 2003

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith

Discret. Appl. Math., 2003

2002

A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search.

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning

Theor. Comput. Sci., 2002

Complexity of Semi-algebraic Proofs.

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Exponential Lower Bound for Static Semi-algebraic Proofs.

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

Algorithms for SAT and Upper Bounds on Their Complexity

Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, Maxim Vsemirnov

Electron. Colloquium Comput. Complex., 2001

Algebraic proof systems over formulas

Dima Grigoriev, Edward A. Hirsch

Electron. Colloquium Comput. Complex., 2001

MAX SAT approximation beyond the limits of polynomial-time approximation.

Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev

Ann. Pure Appl. Log., 2001

Solving Boolean Satisfiability Using Local Search Guided by Unit Clause Elimination.

Edward A. Hirsch, Arist Kojevnikov

Proceedings of the Principles and Practice of Constraint Programming, 2001

2000

New Worst-Case Upper Bounds for SAT.

Edward A. Hirsch

J. Autom. Reason., 2000

SAT Local Search Algorithms: Worst-Case Study.

Edward A. Hirsch

J. Autom. Reason., 2000

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith

Electron. Colloquium Comput. Complex., 2000

Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

Edward A. Hirsch

Electron. Colloquium Comput. Complex., 2000

A New Algorithm for MAX-2-SAT.

Edward A. Hirsch

Proceedings of the STACS 2000, 2000

Worst-case Time Bounds for MAX-k-SAT with respect to the Number of Variables Using Local Search.

Edward A. Hirsch

Proceedings of the ICALP Workshops 2000, 2000

Deterministic Algorithms for <i>k</i>-SAT Based on Covering Codes and Local Search.

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1998

A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments.

Edward A. Hirsch

Log. J. IGPL, 1998

Local Search Algorithms for SAT: Worst-Case Analysis.

Edward A. Hirsch

Proceedings of the Algorithm Theory, 1998

Two New Upper Bounds for SAT.

Edward A. Hirsch

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998