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