Среда 22.04. В.В. Подольский (МИАН, НИУ ВШЭ): "Вычисление функций голосования монотонными формулами маленькой глубины"
Assigned to avs...@gmail.com by me
PDMI seminars
Тема: Вычисление функций голосования монотонными формулами маленькой глубины
Место: Zoom meeting
Время: 22.04.2020, 18:10
Докладчик: В.В. Подольский (МИАН, НИУ ВШЭ)
Abstract:
Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.
Доклад основан на совместной работе с Александром Козачинским: https://eccc.weizmann.ac.il/report/2020/017/
Доклад пройдет в Zoom, необходима регистрация. Для регистрации пройдите по ссылке.
https://zoom.us/meeting/register/tJcucemuqD0oGtLqf7hoIiurxtIqW9P_QRs-
После регистрации вы получите подтверждение по почте с информацией о докладе.
Alexander V. Smal
Напоминаю про сегодняшнее заседание семинара и
про необходимость предварительно зарегистрироваться
для участия.
Саша
> Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/0000000000001af69d05a3789de9%40google.com.
--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia