Edward A. Hirsch - Selected publications#

[1] 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.

[2] E.A. Hirsch, D.Itsykson: On an optimal randomized acceptor for graph nonisomorphism. Information Processing Letters 112(5): 166-171, 2012.

[3] E.A.Hirsch, O.Melanich, S.I.Nikolenko. Feebly secure cryptographic primitives. Zapiski nauchnyh seminarov POMI 399:32-64, 2012.

[4] E. Dantsin, E. A. Hirsch. Worst-Case Upper Bounds. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications. Vol. 185, pp.403-424. IOS Press, 2009.

[5] M.Alekhnovich, E.A.Hirsch, D.Itsykson. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Journal of Automated Reasoning 35(1-3):51-72, 2005.

[6] 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.

[7] J.Gramm, E.A.Hirsch, R.Niedermeier, P.Rossmanith. Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics 130 (2): 139-155, 2003.

[8] D.Grigoriev, E.A.Hirsch, D.V.Pasechnik. Complexity of Semi-Algebraic Proofs. Moscow Mathematical Journal 2(4): 647-679, 2002.

[9] E.Dantsin, A.Goerdt, E.A.Hirsch, R.Kannan, J.Kleinberg, C.Papadimitriou, P.Raghavan, U.Schoning, A Deterministic (2-2/(k+1))^n Algorithm for k-SAT Based on Local Search. Theoretical Computer Science 289/1:69-83, 2002.

[10] E.A.Hirsch, New Worst-Case Upper Bounds for SAT. Journal of Automated Reasoning 24(4): 397-420, 2000.