Разборов, Александр Александрович

В Википедии есть статьи о других людях с такой фамилией, см. Разборов.

Алекса́ндр Алекса́ндрович Разбо́ров (род. 16 февраля 1963 года, Белово, Кемеровская область) — российский и американский математик, член-корреспондент РАН (с 2000 года)^[1], специалист в области теории вычислений. Имеет число Эрдёша, равное 2.^[2]

Александр Александрович Разборов
Дата рождения	16 февраля 1963(1963-02-16) (62 года)
Место рождения	Белово, Кемеровская область, РСФСР, СССР
Страна	Россия  США
Род деятельности	математик, специалист в области информатики
Научная сфера	математик
Место работы	Математический институт им. В. А. Стеклова РАН, Чикагский университет
Альма-матер	МГУ (мехмат)
Учёная степень	д.ф.-м.н. (4 апреля 1991)
Научный руководитель	С. И. Адян
Награды и премии	Премия Неванлинны (1990) Премия Гёделя (2007)
Сайт	people.cs.uchicago.edu/~…

Биография

Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987, диссертация «О системах уравнений в свободной группе»). 4 апреля 1991 года защитил докторскую диссертацию «Нижние оценки сложности вычисления булевых функций» (официальные оппоненты А. Е. Андреев, А. А. Карацуба, А. О. Слисенко)^[3].

С 1991 по 2008 год работал в Математическом институте им. В. А. Стеклова РАН. В 2001—2006 годах — постоянный член Института перспективных исследований Принстонского университета^[4].

С 2008 года — заслуженный профессор в Университете Чикаго (США)^[5][6].

26 мая 2000 года избран членом-корреспондентом РАН по Отделению математических наук.

Научные результаты

В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.

Награды и премии

• Золотая медаль Международной математической олимпиады в Лондоне (1979).
• Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем»^[7]
• Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах».^[8][9]
• Заслуженный профессор (2008) факультета компьютерных наук им. Эндрю МакЛейша в Чикагском университете, США.

Библиография

• Разборов, А. А. Lower bounds for the monotone complexity of some Boolean functions (англ.) // Доклады Академии наук : journal. — 1985. — Vol. 31. — P. 354—357.
• Разборов, А. А. Нижние оценки монотонной сложности логического перманента (рус.) // Математические заметки Академии Наук СССР : журнал. — 1985. — Июнь (т. 37, № 6). — С. 485—493. — doi:10.1007/BF01157687.
• Разборов, Александр Александрович. О системах уравнений в свободной группе (рус.). — Московский государственный университет, 1987. (Кандидатская диссертация. 32.56MB)
• Разборов, А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами (рус.) // Математические заметки Академии Наук СССР : журнал. — 1987. — Апрель (т. 41, № 4). — С. 333—338. — doi:10.1007/BF01137685.
• Razborov, Alexander A. (1989). On the method of approximations (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington (U.S. state), United States. pp. 167–176. doi:10.1145/73007.73023. {{cite conference}}: Неизвестный параметр |Month= игнорируется (справка)
• Razborov, A. A. Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits (англ.) // Mathematical Notes : journal. — 1990. — December (vol. 48, no. 6). — P. 1226—1234. — doi:10.1007/BF01240265.
• Razborov, Alexander A. (1994). Natural proofs (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada. pp. 204–213. doi:10.1145/195058.195134. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка); Неизвестный параметр |month= игнорируется (справка)
• Razborov, Alexander A. Lower Bounds for the Polynomial Calculus (неопр.) // Computational Complexity. — 1998. — December (т. 7, № 4). — С. 291—324. — doi:10.1007/s000370050013.
• Razborov, Alexander A. Propositional proof complexity (англ.) // Journal of the ACM : journal. — 2003. — January (vol. 50, no. 1). — P. 80—82. — doi:10.1145/602382.602406. (Survey paper for JACM’s 50th anniversary)
• Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.

См. также

• Свободная группа
• Односторонняя функция
• Правило резолюций