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

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

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

Н.К. Верещагин, М.Н. Вялый, А.Е. Ромащенко, А.Л. Семенов, А. Шень
Семинар проходит по понедельникам 18:30–20:05 он-лайн (Zoom).
Ссылка на канал YouTube
Объявления о докладах
Записи на доске
Кликните здесь, чтобы увидеть ссылку Zoom

https://us02web.zoom.us/j/83395579459?pwd=dWhrRTNHNGc0WjR4UVVkV1pyOGxvQT09 Meeting ID: 833 9557 9459 Passcode: 716182

Основанный акад. А.Н.Колмогоровым научный семинар посвящен изучению вопросов вычислительной сложности алгоритмических проблем, возникающих как собственно в теории алгоритмов, так и в математической логике, а также другим видам сложности — колмогоровской сложности (сложности описания конечных объектов), коммуникационной сложности и т.п.

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

6 декабря 2021 года. Cheuk Ting Li
« On the Undecidability of Conditional Affine Information Inequalities and Conditional Independence Implication with Cardinality Constraints.«

Доклад состоится в необычное время 12:30 (MSK)

Abstract.
The conditional independence implication problem is to decide whether several statements on the conditional independence among several random variables implies another such statement. For examples, «X indep. of (Y,Z) implies X indep. of Y» is true, whereas «(X indep. of Y, and X indep. of Z) implies X indep. of (Y,Z)» is false. Despite being a fundamental question in probability theory, there is no known algorithm that can solve this problem. It is currently unknown whether this problem is even decidable (i.e., whether such algorithm exists). In this talk, we show that this problem is undecidable if we also allow imposing cardinality constraints (e.g. «X is a binary random variable»). We also show the undecidability of conditional information inequalities if we allow comparison against constants (i.e., affine inequalities). These are proved via a connection between conditional independence implication and the domino problem about tiling the plane with a set of tiles.

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

22 и 29 ноября 2021 года
Доклад А. Козачинского на тему
« Существование цены в играх Блэквелла.«
Аннотация.
В игры Блэквелла играют так. Происходит бесконечно много раундов. На каждом раунде двое игроков играют в конечную матричную игру. Бесконечная последовательность исходов этих матричных игр определяет исход глобальный игры.Оказывается, что у таких игр всегда существует цена в смешанных стратегиях (если функция, оценивающая исходы, борелевская). Это вывел Дональд Мартин из другой своей знаменитой теоремы о разрешимости детерминированных борелевских игр. Я расскажу, как он это сделал.
15 ноября 2021 года
Доклад Н. К. Верещагина на тему
«Подстановочные замощения (substitutional tilings)«.
Аннотация. Пусть дано конечное множество многоугольников. Подстановкой называется способ разрезания каждого из этих многоугольников на несколько многоугольников, каждый из которых подобен одному из исходных с некоторым постоянным коэффициентом подобия k. С каждой подстановкой можно естестественным образом сопоставить семейство замощений плоскости, называемых подстановочными замощениями (связанными с данной подстановкой). Будет рассказано о разных интересных подстановочных замощениях и предложен новый пример семейства подстановочных замощений.
8 November 2021
The talk by Floris Persiau
Randomness & Imprecision: some first steps and open questions
Abstract.
The field of algorithmic randomness studies what it means for infinite (binary) sequences to be random for some given uncertainty model. Classically, such randomness involves precise uncertainty models, and it is only recently that imprecision has been introduced into this field by also allowing for closed probability intervals. As a consequence, the investigation into how imprecision alters our view on random sequences has only just begun. In this talk, I will explain how we allow for non-precise uncertainty models and what additional mathematical
structure is revealed by doing so. Furthermore, I will pose some new questions (e.g., what are the differences between precise and imprecise notions of randomness?) and put some old questions in a new perspective (e.g., what are the differences between Martin-Löf, computable, Schnorr and Church randomness).
1 ноября 2021 года
Доклад А.Шеня  на тему
Теорема Кучеры — Гача: доказательство по Левину.
Аннотация. Теорема говорит, что всякая последовательность нулей и единиц вычислима с некоторым случайным в смысле Мартин-Лёфа оракулом (существует случайная последовательность, к которой она сводится по Тьюрингу). Исходное доказательство строило сводящую машину некоторым искусственным способом, а хотелось воспользоваться тем, что образ равномерной меры при универсальном отображении — максимальная полумера, и всякая последовательность относительно неё в каком-то смысле «случайна». Биенвеню и соавторы доказали, что прямо так этот план не сработает, а Левин придумал, как его исправить и дал простое доказательство как самой теоремы Кучеры-Гача, так и её усилений. Я попробую про это (и про некоторое обобщение его результата) рассказать.
25 октября 2021 года
Доклад Н. К. Верещагина на тему
«Апериодические замощения плоскости равнобедренными прямоугольными треугольниками«.
Аннотация. Можно ли замостить плоскость равнобедренными прямоугольными треугольниками
 двух цветов так, чтобы треугольники соседствовали только по целой стороне, 
причем в этом случае они были разного цвета (аналогично раскраске 
шахматной доски)? Несложно нарисовать такое периодическое замощение.
 Будет рассказано, как после добавления новых цветов на стороны плиток с помощью локальных правил
 их соединения определить естественное семейство таких непериодических замощений.
11 октября и 18 октября 2021 года
Доклад А. Е. Ромащенко на тему
«Бесконечное число нешенноновских информационных неравенств«.

Аннотация. Для набора из k совместно распределенных случайных величин можно вычислить 2^k-1 значений энтропии Шеннона: энтропию каждой из этих величин, энтропию каждой пары, каждой тройки, и т.д. Для данных значений выполняются  «базисные» шенноновские неравенства, например,

H(x) \le H(x,y) (монотонность энтропии,  a.k.a. неотрицательность относительной энтропии)

H(x,y) \le H(x) + H(y)  (субаддитивность, a.k.a. неотрицательность взаимной информации),

H(x,y,z) + H(z) \le H(x,z) + H(y,z) (субмодулярность, a.k.a. неотрицательность относительной взаимной информации).

Известно, что никаких принципиально других линейных неравенств для энтропий пар или троек случайных величин не бывает. Однако для больших наборов величин известны также некоторые «нешенноновские» неравенства дл энтропии, не представимые в виде линейной комбинации базисных. Первое неравенство такого вида было открыто в 1998 году (Z.Zhang, R.W.Yeung).
Мы обсудим теорему Матуша (Frantisek Matus, 2007) о том, что для четверок случайных величин имеется бесконечно много независимых информационных неравенств.
Оригинальная статья:  Frantisek Matus. «Infinitely many information inequalities.» In 2007 IEEE International Symposium on Information Theory, pp. 41-44. IEEE, 2007.

4 октября 2021 года
Доклад Н.К. Верещагина на тему
Преобразование MA протоколов в АМ протоколы с точки зрения количества случайных битов.
Аннотация.
Хорошо известно, что MA включено в AM и в PP.
 Стандартное преобразование MA протокола, в котором количество случайных бит Артура равно a, а длина сообщения
Мерлина равна m, требует O(ma) случайных бит в новом протоколе.
 То же самое верно и для преобразования MA протокола в PP машину.
 В диссертации А.Кнопа был поставлен вопрос, можно ли 
O(ma) заменить на некоторый многочлен только от a.
 Аналогичный вопрос естественно поставить и для PP машин.
 Мы доказываем, что 
 относительно некоторого оракула оба преобразования требуют
 не менее m+a случайных бит. Более того, 
 это же верно и для AM протоколов, в которых вероятность ошибки не отделена от 1/2
 (PP*NP-протоколы), обобщающих как обычные AM протоколы, так 
 и PP машины.
27 сентября 2021 года

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

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

Слайды  | Запись доклада да YouTube

 

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

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

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

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