A clearer picture of approximation resistance
Speaker: Per Austrin, Theory Group, KTH CSC
Time: Fri 2008-09-12 10.15 - Wed 2013-10-23 11.00
Location: 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.