RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар «Глобус» (записи с 2011 года)
29 июня 2018 г. 15:30–16:15, г. Москва, конференц-зал НМУ (Москва, Большой Власьевский пер., 11)
 


Trace reconstruction for the deletion channel

Yuval Peres

Microsoft Research
Видеозаписи:
MP4 646.1 Mb
MP4 1,254.4 Mb
MP4 311.5 Mb

Количество просмотров:
Эта страница:66
Видеофайлы:21

Yuval Peres


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?
The best lower bound known is linear in $n$. Until 2016, the best upper bound was exponential in the square root of $n$. In earlier work with F. Nazarov (STOC 2017), we improved the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle. This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio). Our main new result: If the string $x$ is random, then a subpolynomial number of traces suffices; the proof relies on comparison to a random walk.
(Joint works with Alex Zhai, FOCS 2017 and with Nina Holden & Robin Pemantle, COLT 2017.)

Язык доклада: английский

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018