Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Доказательство нижних оценок с помощью гипотезы ETH
Параметризованные алгоритмы


Что: Лекция
Когда: Среда, 16 декабря 2015, 18:00–19:30
Где: ПОМИ РАН

Описание

  1. ETH, SETH гипотезы и лемма о спарсификации.
  2. Нижняя оценка $O^*(2^{o(n)})$ для задачи о 3-раскраске.
  3. Нижняя оценка $O^*(2^{k\log{k}})$ для задачи о $k \times k$ Клике.
  4. Нижние оценки $O^*(2^{(d\log{d})})$ и $O^*(2^{(d\log{\Sigma})})$ для задачи о ближайшей строке.

Видео