Edward A. Hirsch

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

Collaborative distances:

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

2023

Improving 3N Circuit Complexity Lower Bounds.

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

Comput. Complex., December, 2023

Proving Unsatisfiability with Hitting Formulas.

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

Electron. Colloquium Comput. Complex., 2023

Irreducible Subcube Partitions.

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

Electron. J. Comb., 2023

2022

The power of the Binary Value Principle.

Yaroslav Alekseev, Edward A. Hirsch

Electron. Colloquium Comput. Complex., 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

2018

On the limits of gate elimination.

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

J. Comput. Syst. Sci., 2018

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

2015

Preface.

Juhani Karhumäki, Edward A. Hirsch

Theory Comput. Syst., 2015

On the probabilistic closure of the loose unambiguous hierarchy.

Edward A. Hirsch, Dmitry Sokolov

Inf. Process. Lett., 2015

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

Electron. Colloquium Comput. Complex., 2015

Russian Chapter of European Association for Theoretical Computer Science.

Edward A. Hirsch

Bull. EATCS, 2015

2014

Optimal algorithms and proofs (Dagstuhl Seminar 14421).

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

Dagstuhl Reports, 2014

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

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography.

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

Electron. Colloquium Comput. Complex., 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

2007

An infinitely-often one-way function based on an average-case assumption.

Edward A. Hirsch, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2007

2006

A Complete Public-Key Cryptosystem.

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2006

2005

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

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Electron. Colloquium Comput. Complex., 2005

Time hierarchies for cryptographic function inversion with advice

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2005

Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Edward A. Hirsch, Sergey I. Nikolenko

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

2004

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2004

2003

Algebraic proof systems over formulas.

Dima Grigoriev, Edward A. Hirsch

Theor. Comput. Sci., 2003

Algorithms for SAT based on search in Hamming balls

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Electron. Colloquium Comput. Complex., 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

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

Complexity of semi-algebraic proofs

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

Electron. Colloquium Comput. Complex., 2001

Algorithms for SAT and Upper Bounds on Their Complexity

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

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

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

1999

A New Algorithm for MAX-2-SAT

Edward A. Hirsch

Electron. Colloquium Comput. Complex., 1999

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