Worst-case upper bounds for SAT and lower bounds for SAT algorithms. Upper and lower bounds for semialgebraic proof systems. Optimal heuristic algorithms.
Biography
MSc 1995. PhD 1998. DSc (habilitation) 2012. St.Petersburg Mathematical Society, member of the council. International Computer Science Symposium in Russia (CSR), Steering Committee member.
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.
S. N. Artemov, L. D. Beklemishev, L. Ya. Borkin, A. M. Vershik, E. A. Hirsch, E. Ya. Dantsin, I. A. Ibragimov, E. V. Kalmens, V. Ya. Kreinovich, D. A. Koubenski, A. A. Lodkin, Yu. V. Matiyasevich, B. A. Novikov, V. P. Orevkov, A. L. Semenov, A. O. Slissenko, A. Kh. Shen, “Gregory Samuilovich Tseytin (obituary)”, Russian Math. Surveys, 78:3 (2023), 555–561
2013
2.
M. A. Vsemirnov, È. A. Hirsch, D. Yu. Grigor'ev, G. V. Davydov, E. Ya. Dantsin, I. D. Zaslavskii, È. F. Karavaev, B. Yu. Konev, N. K. Kossovskii, V. A. Lifschitz, M. Margenstern, Yu. V. Matiyasevich, G. E. Mints, V. P. Orevkov, R. Pliuškevičius, A. O. Slisenko, S. V. Solov'ev, V. P. Chernov, “Nikolai Aleksandrovich Shanin (obituary)”, Russian Math. Surveys, 68:4 (2013), 763–767
3.
J. Math. Sci. (N. Y.), 188:1 (2013), 17–34
4.
J. Math. Sci. (N. Y.), 188:1 (2013), 7–16
2010
5.
E. A. Hirsch, D. M. Itsykson, “Infinitely frequently one-sided function based on an assumption on complexity in the mean”, St. Petersburg Math. J., 21:3 (2010), 459–468
2009
6.
E. A. Hirsch, D. Yu. Grigor'ev, K. V. Pervyshev, “Time hierarchies for cryptographic function inversion with advice”, J. Math. Sci. (N. Y.), 158:5 (2009), 633–644
2004
7.
Teoriya slozhnosti vychislenii. IX, Zap. nauchn. sem. POMI, 316, ed. E. A. Girsh, POMI, SPb., 2004
2002
8.
D. Yu. Grigor'ev, E. A. Hirsch, D. V. Pasechnik, “Complexity of semialgebraic proofs”, Mosc. Math. J., 2:4 (2002), 647–679;
Teoriya slozhnosti vychislenii. VII, Zap. nauchn. sem. POMI, 293, ed. E. A. Girsh, POMI, SPb., 2002
2003
10.
M. A. Vsemirnov, E. A. Hirsch, E. Ya. Dantsin, S. V. Ivanov, “Algorithms for SAT and upper bounds on their complexity”, J. Math. Sci. (N. Y.), 118:2 (2003), 4948–4962
2001
11.
M. A. Vsemirnov, E. A. Hirsch, D. Yu. Grigor'ev, G. V. Davydov, E. Ya. Dantsin, A. A. Ivanov, B. Yu. Konev, V. A. Lifshits, Yu. V. Matiyasevich, G. E. Mints, V. P. Orevkov, A. O. Slisenko, “Nikolai Aleksandrovich Shanin (on his 80th birthday)”, Russian Math. Surveys, 56:3 (2001), 601–605
2000
12.
E. A. Hirsch, “Separating sings in the propositional satisfiability problem”, J. Math. Sci. (New York), 98:4 (2000), 442–463
1997
13.
E. A. Hirsch, “On construction of a symbolic realization of hyperbolic automorphisms of the torus”, J. Math. Sci. (New York), 87:6 (1997), 4065–4066
Нижние оценки схемной сложности булевых функций E. A. Hirsch Conference of Professors of the RAS in the Department of Mathematical Sciences of the Russian Academy of Sciences June 16, 2016 11:45
3.
Heuristic proofs E. A. Hirsch General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences December 26, 2011 13:00
Semialgebraic proofs E. Hirsch General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences March 25, 2003
7.
Semialgebraic proofs E. A. Hirsch Meetings of the St. Petersburg Mathematical Society March 25, 2003
8.
“Non-logical” proofs of logical formulas E. A. Hirsch General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences November 20, 2000
Books in Math-Net.Ru
Computational complexity theory. Part IX, Zap. Nauchn. Sem. POMI, 316, ed. E. A. Hirsch, 2004 http://mi.mathnet.ru/book408
Computational complexity theory. Part VII, Zap. Nauchn. Sem. POMI, 293, ed. E. A. Hirsch, 2002 http://mi.mathnet.ru/book386
2023
Contact us: