Коммуникационная сложность функции MIN(x,y) (Арсений Чеканов)

Семинар международной лаборатории теоретической информатики ФКН Алиса и Боб хотят найти минимум двух n-битных чисел, одно знает только Боб, другое — только Алиса. Сколько информации им необходимо передать друг другу, чтобы узнать ответ наверняка? На семинаре, пользуясь математикой не сложнее уровня первого курса, мы докажем, что детерминированная коммуникационная сложность этой задачи равна n Θ(log n), при этом амортизированная коммуникационная сложность равна n. Доклад основан на двух публикациях: Ada et al., The Hardness of Being Private и Ahlswede et al., On communication complexity of vector-valued functions. Выступает Арсений Чеканов, студент четвертого курса бакалавриата «Прикладная математика и информатика» ФКН ВШЭ. 24 октября 2024 Международная лаборатория теоретической информатики: ФКН: ​