Кафедра математической логики и теории алгоритмов

Колмогоровский семинар по сложности вычислений и сложности определений

Руководители:

Н.К. Верещагин, М.Н. Вялый, А.Е. Ромащенко, А.Л. Семенов, А. Шень
Семинар проходит по понедельникам 18:30–20:05 он-лайн (Zoom).
Ссылка на канал YouTube
Объявления о докладах
Кликните здесь, чтобы увидеть ссылку Zoom
https://us02web.zoom.us/j/87821000617?pwd=UzIyblk2bmF2RE5ldndOR01IWlFhZz09
Идентификатор конференции: 878 2100 0617
Код доступа: 579492
Основанный акад. А.Н.Колмогоровым научный семинар посвящен изучению вопросов вычислительной сложности алгоритмических проблем, возникающих как собственно в теории алгоритмов, так и в математической логике, а также другим видам сложности — колмогоровской сложности (сложности описания конечных объектов), коммуникационной сложности и т.п.

Доклады на семинаре.

20 сентября 2021 года

Обсуждение открытых вопросов в колмогоровской сложности.

Слайды

13 сентября 2021 года
Доклад А. Шеня на тему
Открытые вопросы в колмогоровской сложности.

Запись доклада на YouTube | Записи на доске

Аннотация.
По предложению SIGACT, Андрей Ромащенко, Мариус Зиманд и я (Шень) пытаемся собрать некоторые давно открытые и мало изученные вопросы, относящиеся к колмогоровской сложности — их можно будет обсудить на занятии.

Анонсы будущих докладов.

20 сентября 2021 года

Продолжение обсуждения открытых вопросов в колмогоровской сложности.

27 сентября 2021 года

Как нам следует оценивать атлетов и кандидатов

Авторы: Кондратьев А.Ю., Яновский Е.А., Нестеров А.С. (все ВШЭ-СПб)
Аннотация.
Мы изучаем, как ранжировать кандидатов с помощью позиционных балльных правил. Каждая позиция в каждом индивидуальном ранжировании дает определенное количество очков, а общая сумма очков определяет итоговое ранжирование. Мы хотим, чтобы выполнялся принцип согласованности: когда какой-то кандидат удаляется, то итоговое ранжирование остальных кандидатов не меняется. Этот принцип важен в ситуациях, когда множество кандидатов может меняться, а итоговое ранжирование определяет последовательность действий: кого звать на интервью, если лучший претендент отказался? Кому вручать кубок, если победитель был пойман на допинге? Какой фильм рекомендовать к просмотру, если лучший фильм все уже смотрели? Изменится ли результат выборов при добавлении спойлера? К сожалению, полностью согласованных балльных правил не существует, однако, мы можем потребовать более слабую версию согласованности. Существуют балльные правила, которые остаются согласованными, если мы удаляем или добавляем единогласного победителя, например, атлета с подозрительно сильными результатами. Аналогично, мы можем удалять или добавлять единогласного проигравшего, например, спойлера на выборах. Почти ничего не ограничивающие по отдельности, вместе эти два принципа характеризуют однопараметрическое семейство с геометрическими, арифметическими и обратными геометрическими последовательностями очков. Наше семейство содержит три крайних правила: подсчет Борда, медальную систему и обратную медальную систему; мы приводим новые элегантные характеризации этих правил. Затем мы показываем как, эта постановка с одним параметром помогает выбирать подходящие балльные правила для различных приложений.

Страница семинара в базе данных мехмата.См. также: Научные семинары кафедры