Эдуард Алексеевич Гирш

Эдуард Алексеевич Гирш

Дата рождения

26 декабря 1973 года

Место рождения

Благовещенск, РСФСР, СССР

Научная сфера

математика

Эдуард Алексеевич Гирш — российский математик, специалист по теоретической информатике, в.н.с. ПОМИ РАН, д.ф.-м.н., профессор РАН, член Совета по науке Министерства образования и науки РФ.

Ранний период

В 1995 г. окончил мехмат (кафедра Математического обеспечения ЭВМ) СПбГУ.

Карьера

В 1995 г. поступил в аспирантуру лаборатории математической логики ПОМИ РАН.

В 1998 г. стал к.ф.м.н.

С 1999 г. — в.н.с. лаборатории математической логики ПОМИ РАН.

В 2000—2010 гг. — доцент кафедры информатики СПбГУ.

С 2008 г. трудился профессором и завкафедрой Математических и информационных технологий СПАУ.

В 2011 г. стал д.ф.м.н.

Вклад в науку

Его учёная деятельность описывается следующим образом:

Научные интересы и основные результаты Гирша относятся к алгоритмам и теории сложности вычислений. Основные результаты включают в себя новые алгоритмы для задачи выполнимости булевой формулы, экспоненциальные нижние оценки для полуалгебраических систем доказательств, конструкции оптимальных эвристических алгоритмов. Алгоритм для задачи выполнимости k-КНФ (k-SAT), предложенный Гиршем совместно с коллегами в 2002 году, до сих пор является самым быстрым детерминированным алгоритмом для этой задачи.

В совместной работе Э. А. Гирша с Д. Ю. Григорьевым и Д. В. Пасечником была развита теория полуалгебраических систем доказательств — формальных систем, которые используются для доказательств тавтологий, которые основаны на представлении логических выражений при помощи полиномов. Для некоторых таких систем доказаны нижние и верхние оценки.

С Д. М. Ицыксоном разработал теорию эвристических акцепторов — принимающих алгоритмов, которым разрешено иногда ошибаться на некоторых входах. Такой подход позволяет описывать более широкий круг задач, чем традиционные безошибочные алгоритмы. Для эвристических акцепторов, решающих некоторую задачу, доказано безусловное существование оптимального алгоритма (поточечная оптимальность).

Труды

• 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: journal. — Springer, 2012. — Vol. 51. — P. 179—195.
• 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: journal. — Elsevier, 2002. — Vol. 289/1. — P. 69—83.
• E. A. Hirsch. New Worst-Case Upper Bounds for SAT // Journal of Automated Reasoning: journal. — Kluwer Academic Publishers, 2000. — Vol. 24(4). — P. 397—420.
• D. Grigoriev; E. A. Hirsch; D. V. Pasechnik. Complexity of Semi-Algebraic Proofs (неопр.) // Moscow Mathematical Journal. — 2002. — Т. 2(4). — С. 647—679.
• E. Dantsin; E. A. Hirsch. Worst-Case Upper Bounds // Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications (англ.. — IOS Press, 2009. — Vol. 185. — P. 403—424.