Ученые сделали важный шаг к доказательству обратной теоремы Ньюмана

Математики из МГУ имени М.В.Ломоносова сделали важный шаг к доказательству обратной теоремы Ньюмана в теории информации. Последняя работа ученых опубликована в журнале Algorithmica.

По словам одного из авторов, профессора механико-математического факультета МГУ имени М.В.Ломоносова Николая Верещагина, главный результат работы состоит в том, что любой вероятностный коммуникационный протокол с секретными случайными битами можно преобразовать в коммуникационный протокол с общедоступными случайными битами, который вычисляет ту же функцию. При этом информационная сложность нового протокола увеличивается на величину, примерно равную количеству раундов в исходном протоколе. Это преобразование позволяет эффективно сжимать протоколы с небольшим количеством раундов.

В работе использовался метод графов со свойством расширение. Вклад профессора Верещагина состоял в упрощении доказательства основного результата и в доказательстве one-shot варианта теоремы Вольфа-Слепяна.

Сжатие коммуникационных протоколов — активно развивающаяся область теории информации. В работе исследователям удалось сделать шаг вперед на пути доказательства обратной теоремы Ньюмана.