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 октября
Ледовый каток «Родные города»
21-22 сентября 2018 года
ВКК "Белэкспоцентр"

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

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

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

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

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

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

Plain text

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

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

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

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

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

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

 

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

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

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

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

Голоса одноклеточных в пустыне

Последнее изобретение в области звукозаписи — золотая сфера диаметром 60 нм. Его разработчики поставили себе цель записывать звуки, которые издают бактерии и другие одноклеточные организмы.

Ученые МГУ оценили пользу зеленой инфраструктуры в Канаде

Сотрудники географического факультета МГУ оценили функции зеленой инфраструктуры Ванкувера, Торонто и Оттавы, используя новую методику анализа геопространственных данны

Зоопарк в очереди к секвенатору

Еще несколько лет назад расшифровка генома какого-либо живого существа воспринималась как сенсация.

Лекарства для афроамериканцев

В 2005 году FDA (американский Минздрав) впервые одобрило препарат, предназначенный для лечения людей определенной расы.

Удар по голове и вы полиглот!

Существует удивительная загадка человеческого мозга: иногда люди получившие мозговую травму и внезапно обнаруживали, что умеют говорить на иностранном языке, играть на музыкальном инструменте или жонглировать числами.