Прошел семинар лаборатории: "Коммуникационная сложность функции MIN(x,y)"

Прошел семинар лаборатории теоретической информатики 24 октября.

ФКН

На семинаре выступил Арсений Чеканов, студент ПМИ с докладом на тему "Коммуникационная сложность функции MIN(x,y)".

На семинаре было доказано, что детерминированная коммуникационная сложность поставленной задачи равна n + Θ(log n), при этом амортизированная коммуникационная сложность равна n.

Доклад был основан на двух публикациях: Ada et al. — "The Hardness of Being Private"  и Ahlswede et al. — "On communication complexity of vector-valued functions".

Запись семинара представлена ниже.