Edward A. Hirsch

Edward A. Hirsch, Dmitry Itsykson: On an optimal randomized acceptor for graph nonisomorphism. Inf. Process. Lett. 112(5): 166-171 (2012)

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): 179-195 (2012)

Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö, Michail Prilutskii (Eds.): Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings. Lecture Notes in Computer Science 7353, Springer 2012, isbn 978-3-642-30641-9

Evgeny Dantsin, Edward A. Hirsch: Satisfiability Certificates Verifiable in Subexponential Time. SAT 2011: 19-32

Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal: Optimal heuristic algorithms for the image of an injective function. Electronic Colloquium on Computational Complexity (ECCC) 18: 91 (2011)

Edward A. Hirsch, Dmitry Itsykson: On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity. STACS 2010: 453-464

Edward A. Hirsch: Optimal Acceptors and Optimal Proof Systems. TAMC 2010: 28-39

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal: On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Electronic Colloquium on Computational Complexity (ECCC) 17: 193 (2010)

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Groups Complexity Cryptology 1(1): 1-12 (2009)

Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko: Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. JSAT 6(1-3): 53-69 (2009)

Edward A. Hirsch, Sergey I. Nikolenko: A Feebly Secure Trapdoor Function. CSR 2009: 129-142

Evgeny Dantsin, Edward A. Hirsch: Worst-Case Upper Bounds. Handbook of Satisfiability 2009: 403-424

Edward A. Hirsch, Dmitry Itsykson: On optimal heuristic randomized semidecision procedures, with application to proof complexity. CoRR abs/0908.2707 (2009)

Edward A. Hirsch, Dmitry Itsykson: An Infinitely-Often One-Way Function Based on an Average-Case Assumption. WoLLIC 2008: 208-217

Edward A. Hirsch: Exact Algorithms for General CNF SAT. Encyclopedia of Algorithms 2008

Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, Anatol Slissenko (Eds.): Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings. Lecture Notes in Computer Science 5010, Springer 2008, isbn 978-3-540-79708-1

Edward A. Hirsch, Dmitry Itsykson: An infinitely-often one-way function based on an average-case assumption. Electronic Colloquium on Computational Complexity (ECCC) 14(117) (2007)

Edward A. Hirsch, Arist Kojevnikov: Several notes on the power of Gomory-Chvátal cuts. Ann. Pure Appl. Logic 141(3): 429-436 (2006)

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert: Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. CIAC 2006: 60-68

Dima Grigoriev, John Harrison, Edward A. Hirsch (Eds.): Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. Lecture Notes in Computer Science 3967, Springer 2006, isbn 3-540-34166-8

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Electronic Colloquium on Computational Complexity (ECCC) 13 (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): 91-111 (2005)

Laurent Simon, Daniel Le Berre, Edward A. Hirsch: The SAT2002 competition. Ann. Math. Artif. Intell. 43(1): 307-342 (2005)

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reasoning 35(1-3): 51-72 (2005)

Edward A. Hirsch, Sergey I. Nikolenko: Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution. SAT 2005: 135-142

Edward A. Hirsch, Sergey I. Nikolenko: Simulating Cutting Plane proofs with restricted degree of falsity by Resolution. Electronic Colloquium on Computational Complexity (ECCC)(006) (2005)

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: Time hierarchies for cryptographic function inversion with advice. Electronic Colloquium on Computational Complexity (ECCC)(076) (2005)

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert: Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. Electronic Colloquium on Computational Complexity (ECCC)(102) (2005)

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP 2004: 84-96

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert: Algorithms for SAT Based on Search in Hamming Balls. STACS 2004: 141-151

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Electronic Colloquium on Computational Complexity (ECCC)(041) (2004)

Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics 130(2): 139-155 (2003)

Edward A. Hirsch: Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics 130(2): 173-184 (2003)

Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Theor. Comput. Sci. 1(303): 83-102 (2003)

Edward A. Hirsch, Arist Kojevnikov: Several notes on the power of Gomory-Chvatal cuts. Electronic Colloquium on Computational Complexity (ECCC) 10(012) (2003)

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert: Algorithms for SAT based on search in Hamming balls. Electronic Colloquium on Computational Complexity (ECCC)(072) (2003)

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002)

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Exponential Lower Bound for Static Semi-algebraic Proofs. ICALP 2002: 257-268

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of Semi-algebraic Proofs. STACS 2002: 419-430

Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev: MAX SAT approximation beyond the limits of polynomial-time approximation. Ann. Pure Appl. Logic 113(1-3): 81-94 (2001)

Edward A. Hirsch, Arist Kojevnikov: Solving Boolean Satisfiability Using Local Search Guided by Unit Clause Elimination. CP 2001: 605-609

Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Electronic Colloquium on Computational Complexity (ECCC) 8(11) (2001)

Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, Maxim Vsemirnov: Algorithms for SAT and Upper Bounds on Their Complexity. Electronic Colloquium on Computational Complexity (ECCC) 8(12) (2001)

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of semi-algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC)(103) (2001)

Edward A. Hirsch: SAT Local Search Algorithms: Worst-Case Study. J. Autom. Reasoning 24(1/2): 127-143 (2000)

Edward A. Hirsch: New Worst-Case Upper Bounds for SAT. J. Autom. Reasoning 24(4): 397-420 (2000)

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: 69-76

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning: Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search. ICALP 2000: 236-247

Edward A. Hirsch: A New Algorithm for MAX-2-SAT. STACS 2000: 65-73

Edward A. Hirsch: Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search. Electronic Colloquium on Computational Complexity (ECCC) 7(19) (2000)

Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith: New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 7(37) (2000)

Edward A. Hirsch: A New Algorithm for MAX-2-SAT. Electronic Colloquium on Computational Complexity (ECCC) 6(36) (1999)

Edward A. Hirsch: A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments. Logic Journal of the IGPL 6(1): 59-71 (1998)

Edward A. Hirsch: Two New Upper Bounds for SAT. SODA 1998: 521-530

Edward A. Hirsch: Local Search Algorithms for SAT: Worst-Case Analysis. SWAT 1998: 246-254