Направления работы: теоретическая информатика, дискретная математика, комбинаторная теория групп.
Важнейшие результаты: a)Описание множества решений произвольной системы уравнений в свободной группе. б) Нижние оценки размера монотонных булевых схем и размера схем ограниченной глубины в полном базисе с функцией логического сложения. в) Теория "естественных доказательств". г) Нижние оценки в теории сложности доказательств. д) Нижние оценки в теории квантовой коммуникационной сложности. е) Создание теории алгебры флагов и решение на её основе задачи об определении минимально возможного числа треугольников в графе. Ключевые слова теория сложности вычислений, теория сложности доказательств, алгебраические и аналитические методы в комбинаторике |
![]() | ||
![]() |
Наш адрес: 119991 ГСП-1 Москва В-71, Ленинский просп., 14 Телефон: 938-0309 (Справ. бюро) Факс: (495)954-3320 (Лен.пр.,14), (495)938-1844 (Лен.пр.,32а) | ![]() ![]() |