• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Семинар лаборатории теоретической информатики: "Тонкие сводимости". Докладчик: М.Н. Вялый

Мероприятие завершено

Семинар по теме "Тонкое сводимости" состоится в среду, 15 марта.
Врямя проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 505
Заказ пропуска: evavilova@hse.ru

Неформально говоря, сильная гипотеза об экспоненциальном времени (SETH) утверждает, что самый быстрый способ решить задачу выполнимости (k-SAT)

- это вычислить значение КНФ во всех точках. Эта гипотеза настолько сильна, что имеет все шансы оказаться ложной.

В попытках опровержения SETH возникла интересная техника тонких сводимостей (fine-grained reductions). С помощью этой техники можно связывать гипотезы об оптимальном времени решения задач, имеющих очень разную сложность - от экспоненциальной до квадратичной.

В докладе будут даны точные формулировки SETH и fine-grained reductions, приведены простые примеры тонких сводимостей. Кроме того, обсудим, какую роль в этой технике играет лемма о похудании (sparsification lemma).