A clearer picture of approximation resistance
Speaker: Per Austrin, Theory Group, KTH CSC
Tid: Fr 2008-09-12 kl 10.15 - On 2013-10-23 kl 11.00
Plats: room 1439
A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate within a factor better than what is obtained by a random assignment. We talk about recent progress on characterizing approximation resistant CSPs.
Based on joint works with Johan Håstad and Elchanan Mossel.