Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Пятница 29.05. Артур Рязанов (ПОМИ РАН): "Нижние оценки на коммуникационную сложность задач поиска с гаджетом четности и без гаджета"

Speaker: 
Артур Рязанов (ПОМИ РАН)
Date: 
Friday, May 29, 2020 - 18:10
Place: 
Zoom
Abstract: 

В теории сложности доказательств часто рассматривается такая задача поиска: дана невыполнимая формула в КНФ и набор значений ее переменных, требуется найти дизъюнкт формулы, который опровергается этим значением переменных. Известно, что доказательство невыполнимости формулы во многих древовидных системах доказательств можно перестроить в вероятностный коммуникационный протокол для этой задачи поиска. Тем самым для доказательства нижней оценки на сложность древовидного вывода достаточно доказать нижнюю оценку на коммуникационную задачу. Мы будем рассматривать вероятностную коммуникационную сложность для двух участников и k участников в модели "число на лбу".

Первую нижнюю оценку на вероятностную коммуникационную сложность задач поиска получили Бим, Питасси и Сегерлинд (2007), затем Гёс и Питасси (2013) получили более простое доказательства нижней оценки на коммуникационную сложность задачи поиска через его критическую блочную чувствительность. Оба этих результата использую искусственные формулы: в традиционную формулу добавляется гаджет, то есть каждая переменная в формуле заменяется на функцию от свежих переменных, значения которых разделяются между участниками коммуникационного протокола. Мы предлагаем новый способ доказательства нижних оценок на коммуникационную сложность задач поиска, который позволяет получать нижние оценки на естественные формулы.
Таким образом, мы доказываем:
* Точную экспоненциальную нижнюю оценку на сложность опровержения принципа совершенного паросочетания для полного двудольного графа в системе Res($\oplus$).
* Экспоненциальную нижнюю оценку на сложность бинарного принципа Дирихле для древовидных систем, оперирующих строками доказательств, которые можно вычислить с небольшой вероятностной коммуникацией.

Доклад основан на совместной работе с Д. Ицыксоном.

Ссылка на конференцию Zoom будет выслана на рассылку семинара за несколько часов до доклада.



Пятница 22.05. Артур Рязанов (ПОМИ РАН): "Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes"

Speaker: 
Артур Рязанов (ПОМИ РАН)
Date: 
Friday, May 22, 2020 - 18:10
Place: 
Zoom
Abstract: 

Это продолжение предыдущего доклада. Мы рассмотрим взвешенный критерий Стасиса Юкны для доказательства нижних оценок на монотонную вещественную схемную сложность. Затем мы покажем, как его применить для доказательства экспоненциальной нижней оценки на сложность опровержения бинарного принципа Дирихле в системе доказательств Cutting Planes (результат Павла Пудлака и Павла Грубеша).

Ссылка на конференцию Zoom будет отправлена на рассылку семинара за несколько часов до доклада.



Пятница 08.05. Н. Карпов (Indiana University): "Collaborative Top Distribution Identifications with Limited Interaction"

Speaker: 
Н. Карпов (Indiana University)
Date: 
Friday, May 8, 2020 - 18:10
Place: 
Zoom
Abstract: 

В докладе мы рассмотрим задачу поиска среди n распределений m распределений с наибольшим средним. В литературе про обучении с подкреплением эта задача известка как top-m arm identifications и имеет много применений. Мы рассмотрим модель когда несколько игроков пытаются решить задачу в коллаборации. Я расскажу о нашем недавнем результате в котором мы достигаем оптимального trade-off между количеством раундов коммуникации между игроками и числом сэмплов необходимых для решения задачи совместно. В частности я рассажу как сложность задачи поиска m лучших распределений отличается от сложности поиска лучшего распределения.

Доклад будет основан на совместной работе с Qin Zhang и Yuan Zhou: https://arxiv.org/abs/2004.09454 .

Доклад пройдет в Zoom https://iu.zoom.us/j/99855408465?pwd=b1VVTnZMaHFmdzBzVEJsWEd4UjlFZz09

Meeting ID: 998 5540 8465
Password: top100



Пятница 08.05. Артур Рязанов (ПОМИ РАН): "Критерий Юкны для доказательства нижних оценок на монотонные вещественные схемы"

Speaker: 
Артур Рязанов (ПОМИ РАН)
Date: 
Friday, May 8, 2020 - 18:10
Place: 
Zoom
Abstract: 

В докладе мы рассмотрим критерий Стасиса Юкны для оценки сложности вычисления булевых функций монотонными вещественнымт схемами. Монотонная вещественная схема отличается от булевой тем, что в каждый гейт помечен монотонной функцией от двух вещественных переменных. Критерий Юкны связывает монотонную сложность булевой функции с её простыми комбинаторными свойствами.

У доклада планируется продолжение, в котором мы обсудим применение критерия Юкны для получения нижних оценок на сложность доказательств в системе Cutting Plane.

Номер конференции Zoom и пароль будут отправлены на рассылку семинара за несколько часов до доклада.



Среда 22.04. В.В. Подольский (МИАН, НИУ ВШЭ): "Вычисление функций голосования монотонными формулами маленькой глубины"

Speaker: 
В.В. Подольский (МИАН, НИУ ВШЭ)
Date: 
Wednesday, April 22, 2020 - 18:10
Place: 
Zoom meeting
Abstract: 

Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.

Доклад основан на совместной работе с Александром Козачинским: https://eccc.weizmann.ac.il/report/2020/017/

Доклад пройдет в Zoom, необходима регистрация. Для регистрации пройдите по ссылке.
https://zoom.us/meeting/register/tJcucemuqD0oGtLqf7hoIiurxtIqW9P_QRs-
После регистрации вы получите подтверждение по почте с информацией о докладе.


Pages