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

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

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

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

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

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

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

Plain text

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

Другие статьи в этой рубрике

Почему футболист умнее шахматиста?

Чемпионат среди роботов — это своего рода

Жизнь упала с неба

Новые гипотезы ученых: органическое вещество образовалось не на Земле, а одновременно с Землей

 

«Горячая десятка» организмов

Список из десяти самых удивительных живых существ, открытых в минувшем году, составил Международный институт исследования видов при Ун

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

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

Невидимый щит

В статье, опубликованной в журнале Front Line Desk, сообщается, что в радиационных поясах Ван Аллена обнаружен третий пояс, заполненный электронами и протонами высоких энергий.

Химические элементы вступили в должность

Нихоний (Nh), московий (Mc), теннессин (Ts) и оганесон (Og) прошли долгий путь, пока не закрепились в клеточках таблицы Менделеева. В природе этих элементов не существует — для синтеза понадобились годы расчётов и экспериментов.

Вдогонку за алмазами

В далеком 1893 году в пустыне Генри Муассан отыскал метеорит, упавший на Землю когда-то очень давно. Взявшись за изучение внеземного вещества, он нашел в нем маленькие кристаллы неизвестного минерала, который позже назвали муассанитом.

"Столбизм" - как образ жизни

Заповедник нерукотворных каменных исполинов носит прозаическое название «Столбы». Находится он в северо-западных отрогах Восточного Саяна, всего в 7 километрах от Красноярска.

Рекорд натуралиста

«Птицы Америки» — самая дорогая печатная книга, когда-либо проданная на аукционе. Это альбом с иллюстрациями птиц Северной Америки в натуральную величину, выполненными американским натуралистом Дж. Дж. Одюбоном.