Speciality:
01.01.06 (Mathematical logic, algebra, and number theory)
E-mail: Website: https://logic.pdmi.ras.ru/~hirsch Keywords: computational complexity; propositional logic; proof systems.
Subject:
Worst-case upper bounds for SAT and lower bounds for SAT algorithms. Upper and lower bounds for semialgebraic proof systems. Optimal heuristic algorithms.
Main publications:
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. Springer, 2012.
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, Elsevier, 289/1, 2002, pp. 69-83.
E. A. Hirsch. New Worst-Case Upper Bounds for SAT // Journal of Automated Reasoning, 24(4), Kluwer Academic Publishers, 2000, 397–420.
D. Grigoriev, E. A. Hirsch, D. V. Pasechnik. Complexity of Semi-Algebraic Proofs // Moscow Mathematical Journal 2(4): 647-679, 2002.
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.
