теория сложности вычислений,
пропозициональная логика,
системы доказательств.
Основные темы научной работы
Верхние оценки для задачи пропозициональной выполнимости и нижние оценки времени работы некоторых алгоритмов для этй задачи. Верхние и нижние оценки для полуалгебраических систем доказательств. Оптимальные эвристические алгоритмы.
Научная биография:
Окончил мат-мех СПбГУ в 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.
С. Н. Артемов, Л. Д. Беклемишев, Л. Я. Боркин, А. М. Вершик, Э. А. Гирш, Е. Я. Данцин, И. А. Ибрагимов, Е. В. Кальменс, В. Я. Крейнович, Д. А. Кубенский, А. А. Лодкин, Ю. В. Матиясевич, Б. А. Новиков, В. П. Оревков, А. Л. Семенов, А. О. Слисенко, А. Х. Шень, “Григорий Самуилович Цейтин (некролог)”, УМН, 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
2013
2.
М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, И. Д. Заславский, Э. Ф. Караваев, Б. Ю. Конев, Н. К. Косовский, В. А. Лифшиц, М. Маргенштерн, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, Р. Плюшкявичус, А. О. Слисенко, С. В. Соловьев, В. П. Чернов, “Николай Александрович Шанин (некролог)”, УМН, 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
2012
3.
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
4.
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
5.
Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 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
Теория сложности вычислений. VII, Зап. научн. сем. ПОМИ, 293, ред. Э. А. Гирш, ПОМИ, СПб., 2002
2001
10.
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. 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
М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, А. А. Иванов, Б. Ю. Конев, В. А. Лифшиц, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, А. О. Слисенко, “Николай Александрович Шанин (к восьмидесятилетию со дня рождения)”, УМН, 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
1997
12.
Э. А. Гирш, “Принцип разделения знаков для задачи пропозициональной выполнимости”, Исследования по конструктивной математике и математической логике. 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 г.
2023
Обратная связь: