City:
Test
Saint Petersburg
Novosibirsk
Kazan
Language:
Русский
English
About CS Club
Courses
Lecturers
Schools
Login
Registration
Доказательство нижних оценок с помощью гипотезы ETH
Parameterized Algorithms
What:
Lecture
When:
Wednesday, 16 December 2015, 18:00–19:30
Where:
ПОМИ РАН
Description
ETH, SETH гипотезы и лемма о спарсификации.
Нижняя оценка $O^*(2^{o(n)})$ для задачи о 3-раскраске.
Нижняя оценка $O^*(2^{k\log{k}})$ для задачи о $k \times k$ Клике.
Нижние оценки $O^*(2^{(d\log{d})})$ и $O^*(2^{(d\log{\Sigma})})$ для задачи о ближайшей строке.
Video
