теория сложности вычислений,
пропозициональная логика,
системы доказательств.
Основные темы научной работы
Верхние оценки для задачи пропозициональной выполнимости и нижние оценки времени работы некоторых алгоритмов для этй задачи. Верхние и нижние оценки для полуалгебраических систем доказательств. Оптимальные эвристические алгоритмы.
Научная биография:
Окончил мат-мех СПбГУ в 1995 г. Степень к.ф.-м.н. 1998 г. (05.13.17 – теоретические основы информатики). Степень д.ф.-м.н. 2012 г. (01.01.06 – математическая логика, алгебра и теория чисел). Член правления С.-Петербургского математического общества. Член наблюдательного совета конференций CSR (International Computer Science Symposium in Russia).
Основные публикации:
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.
E. A. Hirsch, O. Melanich, S. I. Nikolenko, “Feebly secure cryptographic primitives”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 32–64; J. Math. Sci. (N. Y.), 188:1 (2013), 17–34
2.
E. A. Hirsch, D. M. Itsykson, V. O. Nikolaenko, A. V. Smal, “Optimal heuristic algorithms for the image of an injective function”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 15–31; J. Math. Sci. (N. Y.), 188:1 (2013), 7–16
2009
3.
Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144; 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
Э. А. Гирш, Д. Ю. Григорьев, К. В. Первышев, “Иерархии по времени с неравномерной подсказкой для криптографического обращения функций”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 54–76; 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
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб., 2001, 14–46; 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
Э. А. Гирш, “Принцип разделения знаков для задачи пропозициональной выполнимости”, Исследования по конструктивной математике и математической логике. X, Зап. научн. сем. ПОМИ, 241, ПОМИ, СПб., 1997, 30–71; E. A. Hirsch, “Separating sings in the propositional satisfiability problem”, J. Math. Sci. (New York), 98:4 (2000), 442–463
Э. А. Гирш, “Об одной конструкции символической реализации гиперболических автоморфизмов тора”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. I, Зап. научн. сем. ПОМИ, 223, ПОМИ, СПб., 1995, 137–139; 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
Доказательства с ошибками Э. А. Гирш Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН 26 декабря 2011 г. 13:00
Полуалгебраические доказательства Э. А. Гирш Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН 25 марта 2003 г.