Разборов, Александр Александрович
| Александр Александрович Разборов | |
 Российский учёный, математик, член-корреспондент РАН |
|
| Дата рождения: |
16 февраля 1963 (49 лет) |
|---|---|
| Страна: | |
| Научная сфера: | |
| Место работы: |
Математический институт им. В. А. Стеклова РАН, Чикагский университет |
| Альма-матер: | |
| Научный руководитель: | |
| Известен как: | |
| Награды и премии |
|
Алекса́ндр Алекса́ндрович Разбо́ров (родился 16 февраля 1963 года в Белово Кемеровской обл.) в российский и советский учёный-математик, член-корреспондент РАН, специалист в области теории вычислений, лауреат премии Неванлинны 1990 года за «новый приближённый метод решения алгоритмических проблем»,[1] лауреат премии Гёделя 2007 года (совместно со Стивеном Рудичем) за работу о так называемых «естественных доказательствах».[2][3] Его научным руководителем был Сергей Иванович Адян. Избран членом-корреспондентом Российской Академии наук 26 мая 2000 года.[4] Его число Эрдёша в 2.[5] В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие «естественных доказательствах», класс стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существует, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств. Работает в Математическом институте им. Стеклова РАН и одновременно с 2008 года он является заслуженным профессором департамента компьютерных наук им. Эндрю МакЛейша в Университете Чикаго, США.
Содержание |
[править] Библиография
- Разборов, А. А. (1985). «Lower bounds for the monotone complexity of some Boolean functions» (PDF). Доклады Академии наук 31: 354357.
- Разборов, А. А. (Июнь 1985). «Нижние оценки монотонной сложности логического перманента» (PDF). Математические заметки Академии Наук СССР 37 (6): 485493. DOI:10.1007/BF01157687.
- Разборов Александр Александрович О системах уравнений в свободной группе. в Московский государственный университет, 1987. (Реферат докторской диссертации. 32.56MB)
- Разборов, А. А. (Апрель 1987). «Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами» (PDF). Математические заметки Академии Наук СССР 41 (4): 333338. 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: 167176. DOI:10.1145/73007.73023.
- Razborov, A. A. (December 1990). «Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits» (PDF). Mathematical Notes of the Academy of Sciences of the USSR 48 (6): 12261234. DOI:10.1007/BF01240265.
- Razborov, Alexander A.; Rudich, Stephen (May 1994). "Natural proofs" (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing: 204213. DOI:10.1145/195058.195134.
- Razborov, Alexander A. (December 1998). «Lower Bounds for the Polynomial Calculus» (PostScript). Computational Complexity 7 (4): 291324. DOI:10.1007/s000370050013.
- Razborov, Alexander A. (January 2003). «Propositional proof complexity» (PostScript). Journal of the ACM 50 (1): 8082. DOI:10.1145/602382.602406. (Survey paper for JACM's 50th anniversary)
[править] См. также
[править] Примечания
[править] Ссылки
- Всероссийский математический портал. Персоналии: Разборов Александр Александрович
- Персональная страница А. А. Разборова
- Biography sketch in the Toyota Technological Institute at Chicago.
- Curricula Vitae at the Department of Computer Science, University of Chicago.
- DBLP: Alexander A. Razborov.
- MathSciNet: "Items authored by Razborov, A. A."
- 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.
