Edward A. Hirsch I am a theoretical computer scientist (that is, mathematician) interested in computational complexity and proof theory. News: No good news, unfortunately.

Research papers Teaching Students Affiliations, committees... SAT tools Contacts Personal

Research papers (including surveys and short communications) Y. Alekseev, D. Grigoriev, E. A. Hirsch, I. Tzameret. Semi-Algebraic Proofs, IPS Lower Bounds and the \tau-Conjecture: Can a Natural Number be Negative? ECCC TR19-142 [abstract] [Full text]. Extended abstract appears in Proceedings of STOC-2020, pp.54-67. A. Golovnev, E. A. Hirsch, A. Knop, A. Kulikov. On the Limits of Gate Elimination J. Comput. Syst. Sci. 96: 107-119 (2018) [doi] Extended abstract appears in the Proceedings of MFCS-2016. Preliminary version: ECCC TR16-119 [abstract] [Full text] M. G. Find, A. Golovnev, E. A. Hirsch, A. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. ECCC TR15-166 [abstract] [ Full text, Revision 1: .pdf ]. Extended abstract appears in the Proceedings of FOCS-2016. E. A. Hirsch, D. Sokolov. On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters 115(2015):725-730 [official version] [DOI]. A draft is available as ECCC TR14-050, Revision 1 [abstract] [ Full text: .pdf ]. E. A. Hirsch, D. van Melkebeek, A. Smal. Succinct Interactive Proofs for Quantified Boolean Formulas. Comment #2 to ECCC TR12-077, November 2013 [ .pdf ]. E. A. Hirsch, D. Itsykson. On an optimal randomized acceptor for graph nonisomorphism. Information Processing Letters 112(2012):166-171 [ DOI ]. [Draft: .pdf] E. A. Hirsch, D. Itsykson, V. Nikolaenko, A. Smal. Optimal heuristic algorithms for the image of an injective function. Zapiski nauchnyh seminarov POMI 399:15-31 (2012). [Full text: .pdf] Continues the research started in the previous paper. We study an important special case, where optimal algorithms (not just acceptors) exist in both randomized and deterministic settings. A draft is published as ECCC TR11-091. Will appear also in Journal of Mathematical Sciences (Springer). E. A. Hirsch, D. Itsykson, I. Monakhov, A. Smal. On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Theory of Computing Systems 51(2):179-195, 2012; DOI 10.1007/s00224-011-9354-3. A draft is available as ECCC Report TR10-193 [abstract] [Full text: .pdf]. An early version containing a part of the results appeared as: E. A. Hirsch, D. Itsykson, On optimal heuristic randomized semidecision procedures, with application to proof complexity. Proc. STACS-2010, arXiv:0908.2707v2 [cs.CC]. E. A. Hirsch, Optimal acceptors and optimal proof systems. A survey (invited paper) written for TAMC-2010. [Draft: .pdf] E. A. Hirsch, O. Melanich, S. I. Nikolenko, Feebly secure cryptographic primitives. Zapiski nauchnyh seminarov POMI 399:32-64 (2012). [Draft: .pdf] This is a joint journal version of PDMI preprint 12/2009 by O. Melanich and a paper by E. A. Hirsch and S. I. Nikolenko. Early versions (with some errors not affecting the main result) of the latter paper appeared in Proceedings of CSR-2009, LNCS 5675, Springer, and as PDMI preprint 16/2008. Will also appear in Journal of Mathematical Sciences (Springer)). E. Dantsin, E. A. Hirsch, Satisfiability certificates verifiable in subexponential time. In: Proceedings of SAT 2011, LNCS 6695, pp.19-32. Springer, 2011. E. A. Hirsch, A. Kojevnikov, A. S. Kulikov, and S. I. Nikolenko, Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. Journal on Satisfiability, Boolean Modeling and Computation, Volume 6 (2008), pages 53-69. [Full text: pdf] This paper generalizes E. A. Hirsch, S. I. Nikolenko, Simulating Cutting Plane proofs with restricted degree of falsity by Resolution, ECCC Report TR05-006 [abstract] [Full text: .ps], which also appears in Proceedings of SAT 2005, LNCS 3569, 2005, pp.135-142. E. Dantsin, E. A. Hirsch, Worst-Case Upper Bounds. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications. Vol. 185. IOS Press, 2009, pp.403-424. A new edition of the Handbook is now available at the Publisher's webpage, and the Version of Record is available, and finally the manuscript version of the chapter is available as well. E. A. Hirsch, Exact Algorithms for General CNF SAT. In: Encyclopedia of Algorithms. Springer, 2008. (Reprinted in 2015.) E. A. Hirsch, D. M. Itsykson, An infinitely-often one-way function based on an average-case assumption. ECCC Report TR07-117. [abstract] [Full text: .ps] Proceedings of WoLLIC'08, LNCS 5110, Springer, pp.208-217. Russian journal version: Algebra i Analiz 21(3):129-143, 2009. English translation: St.Petersburg Mathematical Journal 21(3): 459-468, 2010. D. Grigoriev, E. A. Hirsch, K. Pervyshev, A Complete Public-Key Cryptosystem. Groups, Complexity, Cryptology 1(2009). [Publisher's page.] This paper originated from ECCC Report TR06-046 [abstract] [Full text (last modified on April 1, 2006): .ps.gz]. After we published our ECCC report, we were made aware about a recent work of Harnik et al. that predates ours by a year. However, you may still want to read our paper to get the details of the proof (in particular, the construction of the reduction). E. Dantsin, E. A. Hirsch, A. Wolpert, Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. ECCC Report TR05-102. [abstract] [Full text: .ps] Proceedings of CIAC-2006. LNCS 3998, 60-68, Springer, 2006. D. Grigoriev, E. A. Hirsch, K. Pervyshev, Time hierarchies for cryptographic function inversion with advice. ECCC Report TR05-076. [abstract] [Full text: English: .ps, Russian: .ps.gz] Zapiski nauchnyh seminarov POMI, vol. 358, 2008, pp.54-76. M. Alekhnovich, E. A. Hirsch, D. Itsykson, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. ECCC Report TR04-041. [abstract] [Full text: .ps] Extended abstract appears in Proceedings of ICALP 2004, LNCS 3142, 2004, pp.84-96. Full article appears in Journal of Automated Reasoning 35(1-3):51-72, 2005. and is reprinted in the book SAT 2005: Satisfiability Research in the Year 2005 published by Springer in 2006. E. Dantsin, E. A. Hirsch, A. Wolpert, Algorithms for SAT based on search in Hamming balls. ECCC Report TR03-072. [abstract] [Full text: .ps] Extended abstract appears in Proceedings of STACS 2004, LNCS 2996, 2004, pp.141-151. Note that the newer report ECCC TR05-102 listed above contains a better bound. E. A. Hirsch, A. Kojevnikov, Several notes on the power of Gomory-Chvátal cuts. ECCC Report TR03-012. [abstract] [Full text: .ps] Presented at Second St.Petersburg Days of LOGIC and COMPUTABILITY, August 2003. The final version appears in Annals of Pure and Applied Logic 141(3):429-436, 2006. D. Grigoriev, E. A. Hirsch, D. V. Pasechnik, Complexity of semialgebraic proofs. Moscow Mathematical Journal 2(4): 647-679, 2002. [abstract] [Full text (draft version): .ps.gz ] An earlier version appeared as ECCC Report TR01-103. Extended abstracts corresponding to parts of this paper appear in Proceedings of STACS 2002 ("Complexity of semi-algebraic proofs"), LNCS 2285, pp.419-430 [abstract], and Proceedings of ICALP 2002 ("Exponential Lower Bound for Static Semi-algebraic Proofs"), LNCS 2380, pp.257-268 [abstract]. E. A. Hirsch, A. Kojevnikov, UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Annals of Mathematics and Artificial Intelligence 43(1-4):91-111, 2005. [abstract] [Full text (draft): .ps.gz] Preliminary version appeared as PDMI preprint 09/2001 [abstract] [.ps.gz]. A shorter (but more updated) version of this preprint appears in the electronic proceedings of SAT-2002 [.ps]. Extended astract "Solving Boolean satisfiability using local search guided by unit clause elimination" appeared in Proceedings of CP 2001, LNCS 2239, 605-609, 2001. C sources of several implementations of various versions of this algorithm are available. L. Simon, D. Le Berre, E. A. Hirsch, The SAT2002 Competition. Annals of Mathematics and Artificial Intelligence 43(1-4): 307-342, 2005. [abstract] D. Grigoriev, E. A. Hirsch, Algebraic proof systems over formulas. TCS 303/1: 83-102, 2003. [abstract] [Full text (typos fixed 01.03.2004): .ps.gz] Preliminary version appeared in proceedings of LCCS'2001, 113-135, 2001 [abstract] [Full text: .ps.gz] and as ECCC Report TR01-011 [abstract] [Full text: .ps]. E. Dantsin, E. A. Hirsch, S. Ivanov, M. Vsemirnov, Algorithms for SAT and Upper Bounds on Their Complexity. ECCC Report TR01-012. [abstract] [Full text: .ps] This is a survey. A Russian version appears in Zapiski nauchnyh seminarov POMI No.277, 2001, pp.14-46 [Full text: .ps.gz]. English translation: Journal of Mathematical Sciences 118(2):4948-4962, 2003. E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning, A Deterministic (2-2/(k+1))^n Algorithm for k-SAT Based on Local Search. Theoretical Computer Science 289/1, 2002, pp. 69-83. [abstract] [Full text (journal submission): .ps.gz] This paper resulted from merging two independent papers, by the authors #1,#2,#3,#8 and #4,#5,#6,#7. The former paper (E.Dantsin, A.Goerdt, E.A.Hirsch, U.Schöning, "Deterministic algorithms for k-SAT based on covering codes and local search." Proceedings of ICALP'00, LNCS 1853, 236-243, Springer, 2000. [abstract] [ps.gz ((c) Springer-Verlag)] won Best EATCS Paper Award, and this paper is also a result of merging two independent papers, authored by #1,#3 and #2,#8. The former of these two papers is available as PDMI preprint 01/2000 (E.Dantsin, E.A.Hirsch, "Algorithms for k-SAT based on covering codes" [abstract] [Full text: .ps.gz]). E. A. Hirsch, Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics 130/2: 173-184, 2003. [abstract] [Full text (draft): .ps.gz ] An earlier version "Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search" appeared in Proceedings of RANDOM 2000, ICALP Workshops 2000, Proceedings in Informatics 8: 69-76. Carleton Scientific, 2000 [abstract] and as ECCC Report TR00-019 [abstract] [Full text: .ps]. J. Gramm, E. A. Hirsch, R. Niedermeier, P. Rossmanith, New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT. ECCC Report TR00-037. [abstract] [Full text: .ps] A revised version of this paper appears in Discrete Applied Mathematics 130/2: 139-155, 2003. It corresponds to a talk given at SAT-2000 workshop. It makes obsolete the paper E.A.Hirsch, "A 2K/4-time Algorithm for MAX-2-SAT: Corrected Version". ECCC Report TR99-036, Revision 02 [abstract] [.ps] which is a corrected version of ECCC Report TR99-036, Revision 01 ("A New Algorithm for MAX-2-SAT" [abstract] [.ps]), the latter appears in Proceedings of STACS'2000. E. A. Hirsch, SAT Local Search Algorithms: Worst-Case Study. Journal of Automated Reasoning (special issue on SAT) 24(1/2): 127-143, February 2000. [abstract] [Full text (draft): .ps.gz ] This paper is also published in the book "Highlights of Satisfiability Research in the Year 2000", Volume 63 in Frontiers in Artificial Intelligence and Applications, IOS Press, 2000. Parts of this paper were previously published in Proceedings of SWAT'98 ("Local Search Algorithms for SAT: Worst-Case Analysis") and as PDMI preprint 19/1998 ("Hard formulas for SAT local search algorithms" [abstract] [.ps.gz]). E. A. Hirsch, New Worst-Case Upper Bounds for SAT. Journal of Automated Reasoning (2nd special issue on SAT) 24(4): 397-420, 2000. [abstract] [Full text (draft): .ps.gz ] This paper is also published in the book "Highlights of Satisfiability Research in the Year 2000", Volume 63 in Frontiers in Artificial Intelligence and Applications, IOS Press, 2000. Parts of this paper were previously published in Proceedings of SODA'98 ("Two new upper bounds for SAT") and as PDMI preprint 4/1997 ("Deciding satisfiability of formulas with K clauses in less than 20.30897K steps"). E. Ya. Dantsin, E. A. Hirsch, M. R. Gavrilovich, B. Yu. Konev, MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic 113(1-3), pp. 81-94, 2001. [abstract] [Full text (preprint version): .ps.gz ]. Early version appeared as PDMI preprint 14/1998 [abstract] [Full text: .ps.gz ] E. A. Hirsch, Separating sings in the propositional satisfiability problem. Zapiski nauchnyh seminarov POMI No.241, 1997, pp.30-71. English translation: Journal of Mathematical Sciences, Vol.98, No.4, 2000, pp.442-463. [abstract] [Full text in Russian: .ps.gz] [Full text in English (draft): .ps.gz] E. A. Hirsch, A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments. Logic Journal of the IGPL, Vol.6, No.1, Oxford University Press, 1998, pp.59-71. [abstract] [Full text: .ps.gz] Extended abstract of this paper appeared in: KI-95 activities. Workshops, Posters, Demos. Gesselschaft für Informatik, 1995. E. A. Hirsch, On symbolic realization of hyperbolic automorphisms of torus. Zapiski nauchnyh seminarov POMI, No.223, 1995, pp.137-139. English translation: Journal of Mathematical Sciences, Vol.87, No.6, 1997, pp.4065-4066. [abstract] [Full text in English (draft): .tex] [Full text in Russian: .tex] E. A. Hirsch, Picture (array) grammars and plane automata. Unpublished, 1993. [abstract] [email me for full text] Please contact me if you have questions, comments, or problems with getting these papers.

[Laboratory] [Institute]