Перейти к навигации Перейти к поиску
Александр Разборов | |
|---|---|
| Родившийся | 16 февраля 1963 г. |
| Национальность | США, Россия |
| Альма-матер | Московский Государственный Университет |
| Известен | теория групп , логика в информатике , теоретическая информатика |
| Награды | Премия Неванлинны (1990) Премия Гёделя (2007) Премия Дэвида П. Роббинса (2013) |
| Научная карьера | |
| Поля | Математик |
| Учреждения | Чикагский университет , Математический институт им. Стеклова , Технологический институт Toyota в Чикаго |
| Докторант | Сергей Адян |
Александр Александрович Разборов ( русский : Алекса́ндр Алекса́ндрович Разбо́ров ; родился 16 февраля 1963 г.), иногда известный как Саша Разборов , - советский и российский математик и теоретик вычислений . Он является заслуженным профессором службы Эндрю Маклиша в Чикагском университете .
Исследование [ править ]
В своей самой известной работе, проведенной совместно со Стивеном Рудичем , он ввел понятие естественных доказательств - класс стратегий, используемых для доказательства фундаментальных нижних оценок вычислительной сложности . В частности, Разборов и Рудич показали, что в предположении существования определенных видов односторонних функций такие доказательства не могут дать решения проблемы P = NP , поэтому для решения этого вопроса потребуются новые методы.
Награды [ править ]
- Премия Неванлинны (1990 г.) за введение «метода аппроксимации» при доказательстве нижних границ логических схем для некоторых существенных алгоритмических проблем [1]
- Эрдёш, лектор , Еврейский университет Иерусалима , 1998 г.
- Член - корреспондент РАН (2000) [2] [3]
- Премия Дэвида П. Роббинса за статью «О минимальной плотности треугольников в графах» (Combinatorics, Probability and Computing 17 (2008), № 4, 603–618) и за введение нового мощного метода, алгебры флагов, в решать задачи экстремальной комбинаторики
- Премия Гёделя (2007, со Стивеном Рудичем ) за статью « Естественные доказательства ». [4] [5]
- Эндрю Маклиш, заслуженный профессор службы (2008 г.), факультет компьютерных наук Чикагского университета .
- Член Американской академии искусств и наук (AAAS) (2020). [6]
Библиография [ править ]
- Разборов, А.А. (1985). «Нижние оценки монотонной сложности некоторых булевых функций» ( PDF ) . Советская математика - Доклады . 31 : 354–357.
- Разборов А.А. (июнь 1985 г.). «Нижние оценки монотонной сложности логического перманента». Математические заметки АН СССР . 37 (6): 485–493. DOI : 10.1007 / BF01157687 .
- Разборов, Александр Александрович (1987). О системах в свободной группе (PDF) (на русском языке). Московский государственный университет . (Кандидатская диссертация. 32,56МБ)
- Разборов А.А. (апрель 1987 г.). «Нижние оценки размера схем с ограниченной глубиной по полному базису с логическим сложением». Математические заметки АН СССР . 41 (4): 333–338. DOI : 10.1007 / BF01137685 .
- Разборов, Александр Александрович (май 1989 г.). «О методе приближений» (PDF. 1.41MB ) . Материалы 21-го ежегодного симпозиума ACM по теории вычислений . Сиэтл , Вашингтон , США. С. 167–176. DOI : 10.1145 / 73007.73023 .
- Разборов А.А. (декабрь 1990 г.). «Нижние оценки сложности симметричных булевых функций контактно-выпрямительных схем». Математические заметки АН СССР . 48 (6): 1226–1234. DOI : 10.1007 / BF01240265 .
- Разборов Александр А .; Рудич, Стивен (май 1994). «Естественные доказательства» ( PostScript ) . Материалы 26-го ежегодного симпозиума ACM по теории вычислений . Монреаль , Квебек , Канада. С. 204–213. DOI : 10.1145 / 195058.195134 .
- Разборов, Александр Александрович (декабрь 1998 г.). «Нижние оценки для полиномиального исчисления» (PostScript) . Вычислительная сложность . 7 (4): 291–324. CiteSeerX 10.1.1.19.2441 . DOI : 10.1007 / s000370050013 .
- Разборов, Александр Александрович (январь 2003 г.). «Сложность пропозиционального доказательства» (PostScript) . Журнал ACM . 50 (1): 80–82. DOI : 10.1145 / 602382.602406 . (Обзорный доклад к 50-летию JACM)
См. Также [ править ]
- Ави Вигдерсон
- Сложность схемы
- Бесплатная группа
- Естественные доказательства
- Односторонняя функция
- Семейство псевдослучайных функций
- Разрешение (логика)
Примечания [ править ]
- ^ "Международный математический союз: лауреаты премии Рольфа Неванлинны" . Архивировано из оригинала на 2007-12-17.
- ^ "Российская академия наук: Разборов Александр Александрович: Общая информация: История" .
- ^ "Древо российских генеалогических агентств: R" (на русском языке). Архивировано из оригинала на 2007-12-21 . Проверено 15 января 2008 .
- ^ «ACM-SIGACT Awards and Prize: 2007 Gödel Prize» .
- ^ "EATCS: Премия Гёделя - 2007" . Архивировано из оригинала на 2007-12-01.
- ^ «Избранные стипендиаты AAAS» (PDF) . Уведомления Американского математического общества .
Внешние ссылки [ править ]
- Александр Разборов на проекте « Математическая генеалогия» .
- Домашняя страница Александра Разборова .
- Всероссийский математический портал : Персоналии: Разборов Александр Александрович .
- Очерк биографии в Технологическом институте Toyota в Чикаго.
- Биографическая справка факультета компьютерных наук Чикагского университета.
- DBLP: Разборов Александр Александрович .
- Результаты Александра Разборова на Международной математической олимпиаде
- MathSciNet: «Статьи за авторством Разборова А.А.» [ постоянная мертвая ссылка ]
- Работа А. А. Разборова - статья Ласло Ловаса в Трудах Международного конгресса математиков , Киото , Япония, 1990.