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

Доказательство нижних оценок с помощью гипотезы 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})})$ для задачи о ближайшей строке.

Видео

Computer Science Club, 2007–24 гг.