Семинар международной лаборатории теоретической информатики "Коммуникационная сложность функции MIN(x,y)"
Мероприятие завершено
Дата: 24 октября 2024 г., 18:10 - 19:30
Докладчик: Арсений Чеканов, студент ПМИ
Аннотация: Алиса и Боб хотят найти минимум двух n-битных чисел, одно знает только Боб, другое — только Алиса. Сколько информации им необходимо передать друг другу, чтобы узнать ответ наверняка? На семинаре, пользуясь математикой не дальше первого курса, будет доказано, что детерминированная коммуникационная сложность этой задачи равна n + Θ(log n), при этом амортизированная коммуникационная сложность равна n.
Доклад основан на двух публикациях: Ada et al. — "The Hardness of Being Private" и Ahlswede et al. — "On communication complexity of vector-valued functions".
Место проведения: Zoom
Идентификатор конференции: 862 3277 9928
Код доступа: 805160
Дата
24 октября
18:10
В статье упомянуты