Most interesting (Max)-CSPs are APX-hard. In fact, very often the (trivial) approximation ratio achievable in polynomial time cannot be improved even if we allow slightly sub-exponential time, unless the ETH is false. Nevertheless, it has been known since the '90s that density helps in approximating Max-CSPs, and in particular, the work of Arora, Karger and Karpinski established that Max-k-CSP admits a PTAS for instances with \Omega(n^k) constraints.

 

Given that sub-exponential time does not help us approximate Max-CSP in general, the topic of this talk is to examine whether it can help us relax the (strict) density requirement needed for obtaining an approximation scheme. We give an answer that is partly positive and partly negative. On the algorithmic side, we show that by adapting the known exhaustive sampling technique (and using an appropriately larger sample) we can obtain an approximation scheme for Max-k-CSP instances with \Omega(n^{k-1+\delta}) constraints running in (sub-exponential) time 2^{n^{1-\delta}}. For CSPs with arity 2, such as Max CUT, this implies a sub-exponential approximation scheme even for almost sparse instances. On the other hand, we show that this trade-off cannot be extended to instances with fewer than n^{k-1} constraints, and that the running time we obtain is essentially best possible (under the ETH).

 

This is joint work with Dimitris Fotakis and Vangelis Paschos.