Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика»
25 декабря 2018 г. 10:35–11:10, г. Москва, МИАН, ул. Губкина, д. 8, конференц-зал, 9 этаж
 


Полные подграфы в случайных графах и регулярные резолюции

А. А. Разборов

Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Видеозаписи:
MP4 959.3 Mb
MP4 435.7 Mb

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

А. А. Разборов
Фотогалерея


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

Аннотация: Размер максимальной клики в случайном графе Эрдеша-Реньи $G(n,p)$ хорошо известен и практически полностью определяется плотностью графа $p=p(n)$. Однако доказательство того, что почти все графы плотности ниже критической не содержат клику требуемого размера, совершенно неконструктивно и не даёт никаких указаний на то, как этот факт доказывать для индивидуальных графов. Исследование этого вопроса с точки зрения теории сложности доказательств является в настоящее время довольно активной областью, связанной с приложениями в теории комбинаторной оптимизации и криптографии (planted clique) и в теории параметризованной сложности доказательств.
Настоящий доклад основан на совместной работе с Atserias, Bonacina, de Rezende, Laiuria и Nordstrom (STOC 2018), в которой эта задача решена для системы регулярных резолюций. Именно, показывается, что при подходящих значениях параметров любое доказательство отсутствия клики требуемого размера в случайном графе обязано иметь экспоненциальный размер.

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