Разборов, Александр Александрович
Алекса́ндр Алекса́ндрович Разбо́ров (род. 16 февраля 1963 года, Белово, Кемеровская область) — российский и американский математик, член-корреспондент РАН (с 2000 года)[1], специалист в области теории вычислений. Имеет число Эрдёша, равное 2.[2]
| Александр Александрович Разборов | |
|---|---|
 | |
| Дата рождения | 16 февраля 1963 (61 год) |
| Место рождения | |
| Страна |
 Россия  США |
| Научная сфера | математик |
| Место работы | Математический институт им. В. А. Стеклова РАН, Чикагский университет |
| Альма-матер | МГУ (мехмат) |
| Научный руководитель | С. И. Адян |
| Награды и премии |
Премия Неванлинны (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.
См. также править
Примечания править
- ↑ Разборов А.А. - Общая информация. Дата обращения: 3 января 2013. Архивировано 24 августа 2017 года.
- ↑ List of people with Erdős number 2. Дата обращения: 14 ноября 2011. Архивировано 19 апреля 2019 года.
- ↑ https://viewer.rsl.ru/ru/rsl01000340132
- ↑ Computer Science and Discrete Mathematics (CSDM). Дата обращения: 22 марта 2021. Архивировано 23 марта 2021 года.
- ↑ Curriculum Vitae. Дата обращения: 22 марта 2021. Архивировано 31 октября 2021 года.
- ↑ Department of Computer Science. Дата обращения: 12 ноября 2013. Архивировано 25 августа 2013 года.
- ↑ International Mathematical Union: Rolf Nevanlinna Prize Winners. Дата обращения: 14 ноября 2011. Архивировано из оригинала 18 октября 2007 года.
- ↑ 2007 Godel Prize. Дата обращения: 12 апреля 2018. Архивировано из оригинала 3 марта 2016 года.
- ↑ Gödel Prize — 2007. Дата обращения: 12 апреля 2018. Архивировано 12 апреля 2018 года.
Ссылки править
- Профиль Александра Алексеевича Разборова на официальном сайте РАН
- Разборов Александр Александрович на сайте Всероссийского математического портала
- Персональная страница А. А. Разборова
- Biography sketch in the Toyota Technological Institute at Chicago.
- Curricula Vitae at the Department of Computer Science, University of Chicago.
- DBLP: Alexander A. Razborov.
- The Work of A.A. Razborov — an article by László Lovász in the Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990.