FestivalNauki.ru
En Ru
cентябрь-ноябрь 2019
176 городов
September – November 2019
312 cities
11-13 октября 2019
МГУ | Экспоцентр | 90+ площадок
14–16 октября 2016
Центральная региональная площадка
28–30 октября 2016
ИРНИТУ, Сибэскпоцентр
14–15 октября 2016
Центральная региональная площадка
23 сентября - 8 октября 2017
«ДонЭкспоцентр», ДГТУ
ноябрь-декабрь 2018
МВДЦ «Сибирь»,
Вузы и научные площадки города
6-8 октября 2017
Самарский университет
27-29 октября
Кампус ДВФУ, ВГУЭС
30 сентября - 1 октября
Ледовый каток «Родные города»
21-22 сентября 2018 года
ВКК "Белэкспоцентр"
9-10 ноября 2018 года
Мурманский областной Дворец Культуры

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

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

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

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

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

Добавьте свой комментарий

Plain text

  • Переносы строк и абзацы формируются автоматически
  • Разрешённые HTML-теги: <p> <br>
LiveJournal
Регистрация

Новости в фейсбук

Случайные статьи

Окно в мировую науку

Как 25-летний зарубежный опыт работы пригодился в России, почему у лаборатории не было переходного периода после окончания мегагранта и как ученые заглянули из XVIII ве

Раскрыт секрет магического фрукта

В Западной Африке существует растение, которое люди называют не иначе как магическим фруктом. Человек, съевший несколько плодов, перестаёт ощущать кислый вкус, и, например, лимоны для него становятся сладкими.

Ученые обучили нейросеть определять пол человека по написанному тексту

Окололунная орбита

Окололунную орбиту не следует путать с орбитой луны — траекторией движения Луны относительно Земли.

Найти четыре из миллиарда

13 мая 2015 года в журнале Nature вышла в свет статья об открытии, важном для дальнейшего понимания устройства Вселенной.