Strong Lower Bounds on the Approximability of Coloring
Speaker: Lars Engebretsen, NADA, KTH
Tid: Ti 2000-05-23 kl 15.15 - On 2013-10-23 kl 12.00
Plats: room 1537
Abstract:
We describe how the reduction from PCPs to Maximum Clique can be extended to give hardness result for Coloring.