Пятница, 27 февраля, 18:00, к. 106

Пятница, 27 февраля, комната 106. Начало в 18:00.

Докладчик: Н. К. Верещагин (МГУ).

Тема: Генерация строк высокой шенноновской энтропии.

Abstract

Пусть дано натуральное число n. Алиса и Боб хотят, общаясь по телефону, совместно выбрать случайную строку длины n. При этом требуется, чтобы, даже если один из игроков (Алиса или Боб) отклоняется от протокола, выбранная строка была распределена примерно равномерно. Важно, что никаких вычислительных ограничений на жульничающего игрока не накладывается. В докладе будет дан обзор известных результатов о протоколах решения этой задачи. Один из протоколов связан с некоторым интересными результатами из геометрии над конечными полями (решением проблемы Kakeya для конечных полей).