Персоналии
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
 
Гирш Эдуард Алексеевич

Публикаций: 13 (8)
в MathSciNet: 10 (7)
в zbMATH: 6 (5)
в Web of Science: 5 (2)
в Scopus: 5 (4)
Цитированных статей: 5
Цитирований: 50
Лекций и докладов: 8

Статистика просмотров:
Эта страница:1669
Страницы публикаций:5489
Полные тексты:2858
Списки литературы:403
доцент
доктор физико-математических наук (2011)
Специальность ВАК: 01.01.06 (математическая логика, алгебра и теория чисел)
E-mail:
Сайт: https://logic.pdmi.ras.ru/~hirsch
Ключевые слова: теория сложности вычислений, пропозициональная логика, системы доказательств.

Основные темы научной работы

Верхние оценки для задачи пропозициональной выполнимости и нижние оценки времени работы некоторых алгоритмов для этй задачи. Верхние и нижние оценки для полуалгебраических систем доказательств. Оптимальные эвристические алгоритмы.

Научная биография:

Окончил мат-мех СПбГУ в 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.

https://www.mathnet.ru/rus/person11042
https://scholar.google.com/citations?user=p_CnQm0AAAAJ&hl=ru
Список публикаций на ZentralBlatt
https://mathscinet.ams.org/mathscinet/MRAuthorID/629514

Список публикаций:
| научные публикации | по годам | по типам | по числу цит. | общий список |


Цитирования (Crossref Cited-By Service + Math-Net.Ru)

   2023
1. С. Н. Артемов, Л. Д. Беклемишев, Л. Я. Боркин, А. М. Вершик, Э. А. Гирш, Е. Я. Данцин, И. А. Ибрагимов, Е. В. Кальменс, В. Я. Крейнович, Д. А. Кубенский, А. А. Лодкин, Ю. В. Матиясевич, Б. А. Новиков, В. П. Оревков, А. Л. Семенов, А. О. Слисенко, А. Х. Шень, “Григорий Самуилович Цейтин (некролог)”, УМН, 78:3(471) (2023), 170–176  mathnet  crossref  mathscinet  adsnasa  isi; 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  crossref  mathscinet  isi

   2013
2. М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, И. Д. Заславский, Э. Ф. Караваев, Б. Ю. Конев, Н. К. Косовский, В. А. Лифшиц, М. Маргенштерн, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, Р. Плюшкявичус, А. О. Слисенко, С. В. Соловьев, В. П. Чернов, “Николай Александрович Шанин (некролог)”, УМН, 68:4(412) (2013), 173–176  mathnet  crossref  mathscinet  adsnasa  isi  elib; 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  crossref  mathscinet  isi  elib  scopus

   2012
3. E. A. Hirsch, O. Melanich, S. I. Nikolenko, “Feebly secure cryptographic primitives”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 32–64  mathnet  mathscinet; J. Math. Sci. (N. Y.), 188:1 (2013), 17–34  crossref  mathscinet  scopus
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  mathnet  mathscinet; J. Math. Sci. (N. Y.), 188:1 (2013), 7–16  crossref  mathscinet  scopus

   2009
5. Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144  mathnet  mathscinet  zmath  isi; 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  crossref  mathscinet  zmath  isi  scopus 1

   2008
6. Э. А. Гирш, Д. Ю. Григорьев, К. В. Первышев, “Иерархии по времени с неравномерной подсказкой для криптографического обращения функций”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 54–76  mathnet; 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  crossref  scopus 1

   2004
7. Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ред. Э. А. Гирш, ПОМИ, СПб., 2004  mathnet

   2002
8. D. Yu. Grigor'ev, E. A. Hirsch, D. V. Pasechnik, “Complexity of semialgebraic proofs”, Mosc. Math. J., 2:4 (2002), 647–679  mathnet  crossref  mathscinet  zmath  isi; 35
9. Теория сложности вычислений. VII, Зап. научн. сем. ПОМИ, 293, ред. Э. А. Гирш, ПОМИ, СПб., 2002  mathnet

   2001
10. М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб., 2001, 14–46  mathnet  mathscinet  zmath; 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  crossref  mathscinet  zmath 12
11. М. А. Всемирнов, Э. А. Гирш, Д. Ю. Григорьев, Г. В. Давыдов, Е. Я. Данцин, А. А. Иванов, Б. Ю. Конев, В. А. Лифшиц, Ю. В. Матиясевич, Г. Е. Минц, В. П. Оревков, А. О. Слисенко, “Николай Александрович Шанин (к восьмидесятилетию со дня рождения)”, УМН, 56:3(339) (2001), 181–184  mathnet  crossref  mathscinet  zmath  adsnasa  isi; 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  crossref  mathscinet  zmath  isi

   1997
12. Э. А. Гирш, “Принцип разделения знаков для задачи пропозициональной выполнимости”, Исследования по конструктивной математике и математической логике. X, Зап. научн. сем. ПОМИ, 241, ПОМИ, СПб., 1997, 30–71  mathnet  mathscinet  zmath; E. A. Hirsch, “Separating sings in the propositional satisfiability problem”, J. Math. Sci. (New York), 98:4 (2000), 442–463  crossref  mathscinet  zmath 1

   1995
13. Э. А. Гирш, “Об одной конструкции символической реализации гиперболических автоморфизмов тора”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. I, Зап. научн. сем. ПОМИ, 223, ПОМИ, СПб., 1995, 137–139  mathnet  mathscinet  zmath; 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  crossref  mathscinet  zmath

Доклады и лекции в базе данных Math-Net.Ru
1. Сложность (полу)алгебраических доказательств
Э. А. Гирш
Конференция международных математических центров мирового уровня
9 августа 2021 г. 12:10
2. Нижние оценки схемной сложности булевых функций
Э. А. Гирш
Конференция профессоров РАН по Отделению математических наук РАН
16 июня 2016 г. 11:45   
3. Доказательства с ошибками
Э. А. Гирш
Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН
26 декабря 2011 г. 13:00   
4. Оптимальные системы доказательств и алгоритмы (обзор)
Э. А. Гирш
Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
18 декабря 2009 г. 12:00   
5. Сложностная криптография: полные криптосистемы с открытым ключом
Э. А. Гирш, Д. Ю. Григорьев, К. В. Первышев
Заседания Московского математического общества
11 апреля 2006 г.
6. Полуалгебраические доказательства
Э. А. Гирш
Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН
25 марта 2003 г.
7. Полуалгебраические доказательства
Э. А. Гирш
Заседания Санкт-Петербургского математического общества
25 марта 2003 г.
8. «Нелогические» доказательства для логических высказываний
Э. А. Гирш
Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН
20 ноября 2000 г.

Организации
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024