RUS  ENG
Полная версия
СЕМИНАРЫ

Колмогоровский семинар по сложности вычислений и сложности определений
26 ноября 2012 г. 16:45, г. Москва, Главное здание МГУ, ауд. 16-04


A Recent NP-Hardness Result for Approximation of 3-Coloring

Aaron Schild

Аннотация: The speaker will present a recent result by Austrin et al. on the NP-hardness of 3-coloring a 3-colorable graph with at least $\frac{16}{17} + \epsilon$ of the edges bichromatic. Austrin et al.'s result is notable for its use of Fourier analysis over $\mathbb{Z}_3$. He will also review the general approach for developing NP-hardness of approximation results through probabilistically checkable proofs (PCPs) for the label cover proble

Язык доклада: английский


© МИАН, 2024