Abstract k×l of a two-prover game G is a game in which the two provers are sent random sets of questions from G of sizes k and l respectively. These two sets are sampled independently uniformly among all sets of questions of those particular sizes. We prove the following birthday repetition theorem: when G satisfies some mild conditions, val(G k×l ) decreases exponentially in Ω(kl/n) where n is the total number of questions. Our result positively resolves an open question posted by Aaronson, Impagliazzo and Moshkovitz [AIM14] . As an application of our birthday repetition theorem, we obtain new fine-grained hardness of approximation results for dense CSPs. Specifically, we establish a tight trade-off between running time and approximation ratio for dense CSPs by showing conditional lower bounds, integrality gaps and approximation algorithms. In particular, for any sufficiently large i and for every k ≥ 2, we show the following results: • We exhibit an O(q 1/i )-approximation algorithm for dense Max k-CSPs with alphabet size q via O k (i)-level of Sherali-Adams relaxation. • Through our birthday repetition theorem, we obtain an integrality gap of q 1/i forΩ k (i)-level Lasserre relaxation for fully-dense Max k-CSP. • Assuming that there is a constant ε > 0 such that Max 3SAT cannot be approximated to within (1 − ε) of the optimal in sub-exponential time, our birthday repetition theorem implies that any algorithm that approximates fully-dense Max k-CSP to within a q 1/i factor takes (nq)Ω k (i) time, almost tightly matching the algorithmic result based on Sherali-Adams relaxation. As a corollary of our approximation algorithm for dense Max k-CSP, we give a new approximation algorithm for Densest k-Subhypergraph, a generalization of Densest k-Subgraph to hypergraphs. In particular, when the input hypergraph is O(1)-uniform and the optimal k-subhypergraph has constant density, our algorithm finds a k-subhypergraph of density Ω(n −1/i ) in time n O(i) for any integer i > 0.
Manurangsi and Raghavendra REF establish a tight trade-off between running time and approximation ratio for dense Max-r-CSPs for r > 2.
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
ArXiv
ArXiv
Mathematics Computer Science