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

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