Edward A. Hirsch

Publication Activity (10 Years)

Years Active: 1998-2024
Publications (10 Years): 19

Top Topics

Theoretical Computer Science

Propositional Logic

Top Venues

Electron. Colloquium Comput. Complex.

Theory Comput. Syst.

J. Comput. Syst. Sci.

Publications

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