City: Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Wednesday, 16 December 2015, 18:00–19:30
Where: ПОМИ РАН

Description

  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})})$ для задачи о ближайшей строке.

Video