Колмогоровский семинар по сложности вычислений и сложности определений
Руководители:
Семинар проходит по понедельникам 18:30–20:05 он-лайн (Zoom).
Ссылка на канал YouTube
Объявления о докладах
Записи на доске
Анонсы будущих докладов.
23 мая 2022 года.
Доклад М. Андреева и М. Дектярева на тему
Будут рассказаны два доказательства гипотезы, сформулированной в докладе Н. Верещагина. Гипотеза утверждает наличие логарифмического разрыва между полудуплексной коммуникационной сложностью с противником и обычной коммуникационной сложностью для некоторой частичной функции.
Доклады на семинаре.
18 и 25 апреля 2022 года.
Доклад А.В. Смаля на тему
We prove a super-cubic lower bound on the size of a communication
protocol for generalized Karchmer-Wigderson game for some explicit
function f:{0,1}^n -> {0,1}^{log n} . Lower bounds for original
Karchmer-Wigderson games correspond to De Morgan formula lower bounds,
thus the best known size lower bound is cubic. The generalized
Karchmer-Wigderson games are very similar to the original ones, so we
hope that our approach can provide an insight for proving better lower
bounds on the original Karchmer-Wigderson games, and hence for proving
new lower bounds on De Morgan formula size.
To achieve super-cubic lower bound we adapt several techniques used in
formula complexity to communication protocols, prove communication
complexity lower bound for a composition of several functions with a
multiplexer relation, and use a technique from our previous work to
extract the «hardest» function from it. As a result, in this setting
we are able to show that there is a relatively small set of functions
such that at least one of them does not have a small protocol. The
resulting lower bound of Omega(n^{3.156}) is significantly better than
the bound obtained from the counting argument.
В первый раз будут рассказаны основные идеи и высокоуровневое описание доказательств, а во второй раз детали.
4 и 11 апреля 2022 года.
Доклад Н.К. Верещагина на тему
21 марта 2022 года.
Доклад Максима Ушакова на тему
своём опыте использования обучающихся систем работы с текстами и про их
возможности на практике (чего можно добиться, что для этого надо делать
и т.п.) — и попробует что-нибудь показать.
=====
ввод:
Бетховен написал девять симфоний, из которых наиболее известны,
пожалуй,
пятая и девятая. Последняя часть девятой симфонии — хор, который
теперь стал
RuGPT3:
…Симфония была написана в 1809 году, правда сразу же после смерти
Бетховена. Она предназначалась для оркестра, который состоял из 10
инструментов (4 кларнета, 3 гобоя, 2 фагота, 2 валторны, 2 трубы, 2
кларнеты и арфа). Первая часть «Larghetto» была опубликована в виде
фортепианного соло, а во втором произведении симфония уже исполняется в
оркестровом варианте.
В какой-то степени это произведение очень похоже на произведение 19-го
века «Арагонская хота».
В симфониях Бетховен использовал несколько нетрадиционные для того
времени оркестровые средства. В частности, для построения частей часто
витают мелодии из всех симфониц, а оркестранты принимают знаки
дирижера.
Дирижер же управляет игрой инструментов по содержанию.
Вот насколько интересно было композитору сочинять свою первую симфонию!
А еще, есть версия, что именно под влиянием этой симфоники Сталиным
была
написана Симфония номер один. Я уже не помню, по какому поводу была
написана эта симфоничность, но помню, что очень волновалась и
специально
ходила на прослушивание.
Но вот то, что Бетховену удалось создать на удивление цельное творение,
это факт!
14 и 28 марта 2022 года.
Доклад А.Е. Ромащенко на тему
В известной статье Bennett—Gacs—Li—Vitanyi—Zurek (1998) было введено понятие алгоритмического информационного расстояния. Данное расстояние между двумя словами определяется как длина кратчайшей программы, которая переводит заданные объекты друг в друга. Красивый результат, доказанный Bennett et al., утверждает, что длина такой программы (одной программы, выполняющей перевод двух объектов друг к другу в обоих направлениях) примерно равняется максимуму длин двух кратчайших программ, осуществляющих преобразование одного из слов в другое в одном из направлений (т.е., максимум из двух условных колмогоровских сложностей).
Назовем кластером множество слов с достаточно малыми попарными информационными расстояниями. Мы покажем, что в любом плотном кластере (т.е., в кластере, число элементов в котором достаточно велико, а попарные информационные расстояния достаточно малы) можно выделить ядро — такое слово, сложность которого равна взаимной информации для большинства пар слов в кластере, и которое при этом имеет очень малую сложность относительно любого элемента кластера. Иначе говоря, ядро представляет собой материализацию общей информации всех элементов кластера.
Метод выделения ядра кластера используется в частности для доказательства материализации взаимной информации для троек слов.
https://arxiv.org/abs/2110.01346
14 февраля 2022 года.
Доклад Николая Григорьева (Deep Mind) на тему
Языковые модели — механизм вероятностного моделирования языка. В
последние 3-4 года происходит взрывное развитие моделей на базе deep
learning: они становятся все больше и достигают немыслимых ранее
результатов в порождении текста. Я расскажу немного про их историю,
внутреннее устройство и про то, что они умеют, а потом попробую
предположить, куда все это будет развиваться.- Что такое языковая модель
— Зачем они нужны
— Метрики и бенчмарки
— Предыстория: HMM-модели
— Ранние модели на нейронных сетях
— Начало взрыва: Transformer. Механизм внимания (attention)
— Важные модели: ELMO, BERT, GPT-2, Transformer-XL
— Современные большие модели: GPT-3, Gopher, Megatron-Turing
— Чего можно ждать дальше.
6 декабря 2021 года.
Cheuk Ting Li
Доклад состоится в необычное время 12:30 (MSK)
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 года
Доклад Н. К. Верещагина на тему
8 November 2021
The talk by Floris Persiau
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. неотрицательность относительной взаимной информации).
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, Андрей Ромащенко, Мариус Зиманд и я (Шень) пытаемся собрать некоторые давно открытые и мало изученные вопросы, относящиеся к колмогоровской сложности — их можно будет обсудить на занятии.
Страница семинара в базе данных мехмата.См. также: Научные семинары кафедры