Cреда, 22 апреля, Zoom meeting. Начало в 18:10.
Докладчик: В.В. Подольский (МИАН, НИУ ВШЭ).
Тема: Вычисление функций голосования монотонными формулами маленькой глубины.
Abstract
Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.
Доклад основан на совместной работе с Александром Козачинским:
https://eccc.weizmann.ac.il/report/2020/017/Видео доклада:
https://www.youtube.com/watch?v=5HwHGlX16f4