теория сложности вычислений,
пропозициональная логика,
системы доказательств.
Основные темы научной работы
Верхние оценки для задачи пропозициональной выполнимости и нижние оценки времени работы некоторых алгоритмов для этй задачи. Верхние и нижние оценки для полуалгебраических систем доказательств. Оптимальные эвристические алгоритмы.
Научная биография:
Окончил мат-мех СПбГУ в 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
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
9.
С. Н. Артемов, Л. Д. Беклемишев, Л. Я. Боркин, А. М. Вершик, Э. А. Гирш, Е. Я. Данцин, И. А. Ибрагимов, Е. В. Кальменс, В. Я. Крейнович, Д. А. Кубенский, А. А. Лодкин, Ю. В. Матиясевич, Б. А. Новиков, В. П. Оревков, А. Л. Семенов, А. О. Слисенко, А. Х. Шень, “Григорий Самуилович Цейтин (некролог)”, УМН, 78:3(471) (2023), 170–176; 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
10.
М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, И. Д. Заславский, Э. Ф. Караваев, Б. Ю. Конев, Н. К. Косовский, В. А. Лифшиц, М. Маргенштерн, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, Р. Плюшкявичус, А. О. Слисенко, С. В. Соловьев, В. П. Чернов, “Николай Александрович Шанин (некролог)”, УМН, 68:4(412) (2013), 173–176; 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
11.
Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ред. Э. А. Гирш, ПОМИ, СПб., 2004
12.
Теория сложности вычислений. VII, Зап. научн. сем. ПОМИ, 293, ред. Э. А. Гирш, ПОМИ, СПб., 2002
13.
М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, А. А. Иванов, Б. Ю. Конев, В. А. Лифшиц, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, А. О. Слисенко, “Николай Александрович Шанин (к восьмидесятилетию со дня рождения)”, УМН, 56:3(339) (2001), 181–184; 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
Доказательства с ошибками Э. А. Гирш Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН 26 декабря 2011 г. 13:00
Полуалгебраические доказательства Э. А. Гирш Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН 25 марта 2003 г.
Обратная связь: