Skip to main content
To KTH's start page

Strong Lower Bounds on the Approximability of Coloring

Speaker: Lars Engebretsen, NADA, KTH

Time: Tue 2000-05-23 15.15 - Wed 2013-10-23 12.00

Location: room 1537

Export to calendar

Abstract:

We describe how the reduction from PCPs to Maximum Clique can be extended to give hardness result for Coloring.

To the calendar