Миша Алехнович

1978-2006

Миша Алехнович родился в Москве 26 октября 1978 года. В 1991-м Миша начал учиться в 8Б классе 57 школы, и в 1995-м поступил в МГУ им. М.В.Ломоносова на механико-математический факультет. В 2000-м Миша окончил мехмат с красным дипломом, в 2000-2001 участвовал в специальной программе по теории сложности, проводимой Институтом Перспективных Исследований (Insitute for Advanced Study) в Принстоне, США, а в 2001-2003 учился в аспирантуре в Массачусетском Технологическом Институте (MIT). Получив ученую степень (PhD) в 2003, Миша вернулся в Принстон, IAS и провел там следующие два года (2003-2005). В 2005 он начал работать на факультете математики в Калифорнийском Университете Сан-Диего.

Миша трагически погиб в водном походе 5 августа 2006 года в возрасте 27 лет.

Его ранняя смерть приостановила начавшуюся - и, несомненно, продолжившуюся бы - яркую и многообещающую карьеру в области Theoretical Computer Science. Миша начал работу в теории сложности доказательств, одном из наиболее трудных подразделов теории сложности, куда он внес весьма впечатляющий вклад. Отмечая некоторые из его результатов, в [1] и [2] Миша изучал основополагающий вопрос об автоматизируемости различных систем доказательств и доказал сильные (условные) результаты о невозможности такой автоматизируемости. Эти результаты остаются непревзойденными; они установили неожиданную связь между сложностью доказательств и другими областями, такими как вероятностно проверяемые доказательства (PCP) или теория параметризованной сложности. Работы [3,4] закладывают основы теории псевдослучайных генераторов в сложности доказательств и показывают, как построить такие генераторы для многих нетривиальных систем. Эта теория остается одним из немногих имеющихся разумных подходов к центральной и широко открытой проблеме в теории сложности доказательств. Статьи [5, 6] дают строгие нижние оценки для конкретных систем доказательств, и вновь, эти результаты сегодня остаются одними из самых сильных.

В последние годы Миша также начал применять наработанный им в сложности доказательств опыт в смежных областях. Он уже сделал несколько интересных шагов в этом направлении и, незадолго до трагедии, активно работал над двумя многообещающими исследовательскими проектами. Отмечая некоторые из его достижений, в работе [7] устанавливаются сильные нижние оценки в теории proper learning, основанные на новых и оригинальных связях с автоматизируемостью систем доказательств. [8] доказывает очень интересные результаты про внутренние ограничения методов, базируемых на полуопределённой релаксации; эти методы весьма популярны среди специалистов по теории алгоритмов. В [9] установлены сильние нижние оценки сложности решения задачи ВЫПОЛНИМОСТЬ в ограниченной, но естественной (и также очень популярной) модели.

Помимо того, что Миша был по-настоящему восходящей звездой, он оставался приятным, веселым и обаятельным человеком. Для многих из нас он стал настоящим другом, не только коллегой или соавтором. Нам всем будет его не хватать.

А. Разборов

Оригинал статьи здесь:
http://www.mi.ras.ru/~razborov/misha_sigact.pdf

Список литературы

-----------------

[1] M. Alekhnovich, S. Buss, S. Moran, and T. Pitassi. Minimum propositional proof length is $NP$-hard to linearly approximate. Journal of Symbolic Logic, 66:171--191, 2001.

[2] M. Alekhnovich and A. Razborov.
Resolution is not automatizable unless W[P] is tractable.
Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 210--219, 2001.

[3] M. Alekhnovich, E. Ben-Sasson, A. Razborov, and A. Wigderson.
Pseudorandom generators in propositional proof complexity.
SIAM Journal on Computing, 34(1):67--88, 2004.

[4] M. Alekhnovich and A. Razborov.
Lower bounds for the polynomial calculus: non-binomial case.
Proceedings of the Steklov Institute of Mathematics, 242:18--35, 2003.

[5] M. Alekhnovich, J. Johannsen, T. Pitassi, and A. Urquhart.
An exponential separation between regular and general resolution.
In Proceedings of the 34th ACM Symposium on the Theory of Computing, pages 448--456, 2002.

[6] M. Alekhnovich.
Lower bounds for k-DNF resolution on random 3-CNFs.
In Proceedings of the 37th ACM Symposium on the Theory of Computing, pages 251--256, 2005.

[7] M. Alekhnovich, M. Braverman, V. Feldman, A. R. Klivans, and T. Pitassi.
Learnability and automatizability.
In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 621--630, 2004.

[8] M. Alekhnovich, S. Arora, and I. Tourlakis.
Toward strong nonapproximability results in the Lovasz-Schrijver hierarchy.
In Proceedings of the 46th ACM Symposium on the Theory of Computing, pages 294--303, 2005.

[9] M. Alekhnovich, E. Hirsch, and D. Itsykson.
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas.
In Proceedings of the 31st ICALP, pages 84--96, 2004.