Лаборатория алгоритмических методов

Научные результаты:

• Улучшена нижняя оценка на размеры булевых схем. Эта оценка не только устанавливает новый мировой рекорд на размеры подобных схем, но и является первым (с 1984 года) улучшением известных нижних границ для одной из наиболее фундаментальных моделей вычислений.
• Решены фундаментальные задачи о сложности вычислений гомоморфизмов графов и подграфов. Нахождение точных асимптотических оценок сложности для этих задач являлось одним из центральных открытых вопросов в области экспоненциальных алгоритмов.
• Получены первые параметризованные алгоритмы для задачи о надстроке, которая является математической моделью задачи сборки генома.
• Разработан метод доказательства теоремы об иерархии по времени для эвристических вычислений с помощью иерархии по времени моделирования распределений. Теоремы об иерархии по времени являются основным инструментом, используемым для решения важнейшей задачи теории сложности – разделения классов сложности.

Образование и подготовка кадров:

• Проведены 3 международные студенческие школы: Студенческая научная школа по алгоритмам и теории сложности в 2014 году (80 участников), две студенческие школы “Recent Advances in Algorithms” в 2017 (70 участников) и в 2018 (50 участников) годах.

• Защиты: 1 докторская диссертация, 4 кандидатских диссертации по направлению научного исследования.

• Ежегодно в состав лаборатории принимаются 1-2 новых аспиранта, проходящих обучение в ПОМИ РАН под руководством членов научного коллектива. В настоящий момент в состав лаборатории входят 5 аспирантов, 7 кандидатов наук. Среди 5 докторов наук, входящих в состав лаборатории, один имеет звание академика РАН и один – член-корр. РАН.

• Разработаны и проведены 12 курсов лекций по теоретической информатике для программ бакалавриата, магистратуры и аспирантуры, курсы повышения квалификации молодых специалистов. Программы магистратуры: «Анализ булевых функций», «Эффективные алгоритмы», «Теория сложности доказательств», «Параметризованные алгоритмы», «Теоретико-сложностные основы криптографии.», «Практическое программирование и анализ данных в специализированных средах», «Теория информации». Программы бакалавриата: «Математическая логика и теория алгоритмов» «Теория алгоритмов», «Основы дискретной математики и математической логики». Программы повышения квалификации: «Алгоритмы обработки потоковых данных», «Алгоритмы для NP- трудных задач». Курсы читались на базе Научно-образовательного центра нанотехнологий РАН (Россия), Санкт-Петербургского национального исследовательского Академического университета РАН (Россия), Казанского федерального университета (Россия), Научно-образовательного центра при ПОМИ РАН, Высшей школы экономики (Россия) и Санкт-Петербургского государственного университета (Россия).

• Организованы регулярные курсы лекций специалистов в области алгоритмов и теоретической информатики для повышения квалификации научного коллектива, а также студентов, аспирантов и сотрудников сторонних организаций Санкт-Петербурга. Около 10 открытых курсов лекций проводятся каждый семестр на базе ПОМИ РАН (видеозаписи лекций опубликованы на сайте Computer Science Club).

Организационные и инфраструктурные преобразования:

На базе лаборатории сформирован некоммерческий научно-образовательный центр, в котором каждый год проводится около двадцати открытых курсов по теоретической информатике и программированию. Курсы читаются действующими учеными и практикующими специалистами. Видеозаписи и материалы всех курсов опубликованы в открытом доступе сайте Computer Science Club.

Другие результаты:

• Организовано несколько крупных международных конференций по алгоритмам и теории сложности: Third St. Petersburg Days of Logic and Computability 2015, 11th International Computer Science Symposium in Russia 2016, 15th International Symposium on Experimental Algorithms 2016, Journées sur les Arithmétiques Faibles 2017, «Машинное обучение и анализ алгоритмов в Санкт-Петербурге 2017». Институт посетили более 200 ведущих российских и международных специалистов в области теории алгоритмов и компьютерных наук.

• Сотрудники лаборатории являются руководителями более 10 проектов, получивших гранты, в том числе гранты Российского фонда фундаментальных исследований, Российского научного фонда, Совета по грантам Президента Российской Федерации и других бюджетных и коммерческих организаций.

• Ежегодно сотрудники лаборатории заключают коммерческие контракты на проведение исследований и подготовку курсов лекций с такими организациями как Яндекс, Исследовательский центр Samsung, Huawei и др.

• Члены научного коллектива регулярно выступают с докладами на международных симпозиумах и конференциях по всему миру.
  

Сотрудничество:

• Университет Бергена (Норвегия), Институт математических наук Ченнаи (Индия), Варшавский университет (Польша), Калифорнийский университет в Сан-Диего (США), Университет Турку (Финляндия), Курантовский институт математических наук (США): совместные исследования и научные публикации.

• Институт Ченнаи (Индия), Университет Бергена (Норвегия): разработаны новые эффективные алгоритмы для трудных задач на графах и строках.

• Варшавский университет: получены новые условные нижние оценки для задач вложения графов.

• Калифорнийский университет в Сан-Диего: записано две онлайн-специализации на международной платформе Coursera, на них в данный момент записаны более двухсот тысяч слушателей со всего мира.