ЭС: А.А.Разборов

РАЗБОРОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ (р. 16.02.1963, Белово Кемеровской обл.), математик.

 

Окончил механико-математический факультет МГУ (1987). Ученик С.И. Адяна.

Кандидат физико-математических наук (1987, «О системах уравнений в свободных группах»). Доктор физико-математических наук (1991, «Lower bounds in the Boolean Complexity»).

Член-корреспондент отделения математики РАН (2000).

Член Американской академии искусств и наук/American Academy of Arts and Science (2020).

 

Научная деятельность. В сфере научных интересов теоретическая информатика, дискретная математика, теория вычислений, теория сложности доказательств, комбинаторная теория групп, алгебраические и аналитические методы в комбинаторике.

Ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности (соавтор). Дал описание множества решений произвольной системы уравнений в свободной группе. Установил нижние оценки размера монотонных булевых схем и размер схем ограниченной глубины в полном базисе с функцией логического сложения; нижние оценки в теории сложности доказательств, нижние оценки в теории квантовой коммуникационной сложности. Разработал метод, называемый алгеброй флагов, оказавший значительное влияние на использование компьютеров для поиска решений со строгими доказательствами задач экстремальной комбинаторики.

 

Литература: Alexander Razborov's Home Page; А.А.Разборов. РАН.