Seminars

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


Пятница 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-
После регистрации вы получите подтверждение по почте с информацией о докладе.

Пятница 27.12. Дмитрий Соколов: "Trade-offs Between Size and Degree in Polynomial Calculus"

Speaker: 
Дмитрий Соколов
Date: 
Friday, December 27, 2019 - 17:00
Place: 
ауд. 106
Abstract: 

Building on [Clegg et al.~'96], [Impagliazzo et al.~'99] established that if an unsatisfiable $k$-CNF formula over $n$~variables has a refutation of size~$S$ in the polynomial calculus resolution proof system, then this formula also has a refutation of degree $k + O(\sqrt{n \log S})$. The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen~'16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.

Pages