[ONLINE] Семинар МЛ ТИ и ПОМИ РАН: "Вычисление функций голосования монотонными формулами маленькой глубины"

Доклад Владимира Подольского  "Вычисление функций голосования монотонными формулами маленькой глубины."

Аннотация:

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

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

Доклад пройдет в zoom, необходима регистрация.