Окончил механико-математический факультет МГУ (1981).
Кандидат физико-математических наук (1984). Доктор физико-математических наук (1995). Профессор (1997).
Профессор кафедры математической логики и теории алгоритмов механико-математического факультета (1998 - н. вр.).
Область научных интересов: сложность вычислений, колмогоровская сложность, разрешимые теории.
Тема кандидатской диссертации «Алгоритмические проблемы для линейных рекуррентных последовательностей». Тема докторской диссертации «Релятивизируемость в структурной теории сложности вычислений».
Читает курсы «Математическая логика и теория алгоритмов», «Геометрия и топология», «Теоретико-сложностные проблемы криптографии», «Сложность вычислений», «Колмогоровская сложность», «Коды, исправляющие ошибки», «Метод вынуждения», «Коммуникационная сложность», «Алгоритмические методы в теории сложности».