Alexander Razborov

Alexander Razborov
Razborov in Oberwolfach , 2024
Рожденный	( 1963-02-16 ) 16 февраля 1963 г. Белово , РСФСР , СССР.
Национальность	Американская, Русская
Альма-матер	Московский Государственный Университет
Известный	теория групп , логика в информатике , теоретическая информатика
Награды	Премия Неванлинны (1990) Премия Гёделя (2007). Гёдельская лекция (2010) Премия Дэвида П. Роббинса (2013)
Научная карьера
Поля	Математик
Учреждения	Чикагский университет , Математический институт им. Стеклова , Технологический институт Тойота в Чикаго
Докторантура	Сергей Адян

Александр Александрович Разборов ( русский : Александр Александрович Разборов ; родился 16 февраля 1963 года), иногда известный как Саша Разборов , — советский и российский математик и теоретик вычислительной техники . Он является заслуженным профессором службы Эндрю Маклиша в Чикагском университете .

Исследовать

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

Награды

• Премия Неванлинны (1990) за внедрение «метода аппроксимации» при доказательстве булевых схем нижних границ некоторых важных алгоритмических задач,
• Преподаватель Эрдеша , Еврейский университет в Иерусалиме , 1998 г.
• Член-корреспондент ( РАН 2000).
• Премия Гёделя (2007, со Стивеном Рудичем ) за статью « Естественные доказательства ».
• Премия Дэвида П. Роббинса за статью «О минимальной плотности треугольников в графах» (Combinatorics, Probability and Computing 17 (2008), № 4, 603–618), а также за введение нового мощного метода — алгебр флагов — для решать задачи по экстремальной комбинаторике
• Преподаватель Гёделя (2010 г.) с лекцией « Сложность доказательств высказываний».
• Эндрю Маклиш, заслуженный профессор (2008 г.) факультета компьютерных наук Чикагского университета .
• Член Американской академии искусств и наук (AAAS) (2020).

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

• Разборов, А.А. (1985). «Нижние оценки монотонной сложности некоторых булевых функций» (PDF) . Советская математика — Доклады . 31 : 354–357.
• Разборов А.А. (июнь 1985 г.). «Нижние границы монотонной сложности логического перманента». Математические записки Академии наук СССР . 37 (6): 485–493. дои : 10.1007/BF01157687 . S2CID   120875831 .
• Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (in Russian). Московский государственный университет . (PhD thesis. 32.56MB)
• Разборов А.А. (апрель 1987 г.). «Нижние границы размера схем ограниченной глубины на полном базисе с логическим сложением». Математические записки Академии наук СССР . 41 (4): 333–338. дои : 10.1007/BF01137685 . S2CID   121744639 .
• Разборов, Александр А. (май 1989 г.). «Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89». Материалы 21-го ежегодного симпозиума ACM по теории вычислений . Сиэтл , Вашингтон , США. стр. 167–176. дои : 10.1145/73007.73023 . ISBN  0897913078 .
• Разборов А.А. (декабрь 1990 г.). «Нижние оценки сложности симметричных булевых функций контактно-выпрямительных схем». Математические записки Академии наук СССР . 48 (6): 1226–1234. дои : 10.1007/BF01240265 . S2CID   120703863 .
• Разборов, Александр А.; Рудич, Стивен (май 1994 г.). «Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '94». Материалы 26-го ежегодного симпозиума ACM по теории вычислений . Монреаль , Квебек , Канада. стр. 204–213. дои : 10.1145/195058.195134 . ISBN  0897916638 .
• Разборов, Александр А. (декабрь 1998 г.). «Нижние границы полиномиального исчисления» (PostScript) . Вычислительная сложность . 7 (4): 291–324. CiteSeerX   10.1.1.19.2441 . дои : 10.1007/s000370050013 . S2CID   8130114 .
• Разборов, Александр А. (январь 2003 г.). «Сложность доказательства высказываний» (PostScript) . Журнал АКМ . 50 (1): 80–82. дои : 10.1145/602382.602406 . S2CID   17351318 . (Обзорный доклад к 50-летию JACM)

См. также

• Ави Вигдерсон
• Сложность схемы
• Бесплатная группа
• Естественные доказательства
• Односторонняя функция
• Семейство псевдослучайных функций
• Разрешение (логика)

Внешние ссылки

• Александр Разборов в проекте «Математическая генеалогия» .
• Alexander Razborov's Home Page .
• All-Russian Mathematical Portal : Persons: Razborov Alexander Alexandrovich .
• Очерк биографии в Технологическом институте Тойоты в Чикаго.
• Биографическая справка на факультете компьютерных наук Чикагского университета.
• DBLP: Alexander A. Razborov .
• Результаты Александра Разборова на Международной математической олимпиаде
• Работа А.А. Разборова – статья Ласло Ловаса в Трудах Международного конгресса математиков , Киото , Япония, 1990.