A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

A (k x l)-birthday repetition G^{k x 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 x l}) decreases exponentially in Omega(kl/n) where n is the total number of questions. Our result positively resolves an open question posted by Aaronson, Impagliazzo and Moshkovitz [Aaronson et al., CCC, 2014]. As an application of our birthday repetition theorem, we obtain new fine-grained inapproximability results for dense CSPs. Specifically, we establish a tight trade-off between running time and approximation ratio 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: - 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 Omega_k(i / polylog i)-level Lasserre relaxation for fully-dense Max k-CSP. - Assuming that there is a constant epsilon > 0 such that Max 3SAT cannot be approximated to within (1 - epsilon) 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)^{Omega_k(i / polylog i)} time, almost tightly matching our algorithmic result. As a corollary of our algorithm for dense Max k-CSP, we give a new approximation algorithm for Densest k-Subhypergraph, a generalization of Densest k-Subgraph to hypergraphs. When the input hypergraph is O(1)-uniform and the optimal k-subhypergraph has constant density, our algorithm finds a k-subhypergraph of density Omega(n^{?1/i}) in time n^{O(i)} for any integer i > 0