WikiSort.ru - Не сортированное

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

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

Биография

Выпускник московской физико-математической школы №2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987). Доктор физико-математических наук (1991).

Работает в Университете Чикаго (США)^[3] и в Математическом институте им. В. А. Стеклова РАН.

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

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

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

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

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

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

• Разборов, А. А. (1985). “Lower bounds for the monotone complexity of some Boolean functions” (PDF). Доклады Академии наук. 31: 354—357.
• Разборов, А. А. (Июнь 1985). “Нижние оценки монотонной сложности логического перманента”. Математические заметки Академии Наук СССР (PDF)|format= требует |url= (справка на английском). 37 (6): 485—493. DOI:10.1007/BF01157687. Используется устаревший параметр |month= (справка)
• Разборов, Александр Александрович. О системах уравнений в свободной группе : []. — Московский государственный университет, 1987. (Кандидатская диссертация. 32.56MB)
• Разборов, А. А. (Апрель 1987). “Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами”. Математические заметки Академии Наук СССР (PDF)|format= требует |url= (справка на английском). 41 (4): 333—338. DOI:10.1007/BF01137685. Используется устаревший параметр |month= (справка)
• Razborov, Alexander A. (1989). "On the method of approximations" (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing: 167–176. DOI:10.1145/73007.73023. 
• Razborov, A. A. (December 1990). “Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits”. Mathematical Notes of the Academy of Sciences of the USSR (PDF)|format= требует |url= (справка на английском). 48 (6): 1226—1234. DOI:10.1007/BF01240265. Используется устаревший параметр |month= (справка)
• Razborov, Alexander A.; Rudich, Stephen (May 1994). "Natural proofs" (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing: 204–213. DOI:10.1145/195058.195134. 
• Razborov, Alexander A. (December 1998). “Lower Bounds for the Polynomial Calculus” (PostScript). Computational Complexity. 7 (4): 291—324. DOI:10.1007/s000370050013. Используется устаревший параметр |month= (справка)
• Razborov, Alexander A. (January 2003). “Propositional proof complexity” (PostScript). Journal of the ACM. 50 (1): 80—82. DOI:10.1145/602382.602406. Используется устаревший параметр |month= (справка) (Survey paper for JACM’s 50th anniversary)
• Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.

См. также

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

Примечания

Ссылки

• Профиль Александра Алексеевича Разборова на официальном сайте РАН
• Разборов Александр Александрович на сайте Всероссийского математического портала
• Персональная страница А. А. Разборова
• 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.