A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

Pasin Manurangsi, Prasad Raghavendra

A $(k\times l)$-birthday repetition ${\mathcal{G}}^{k\times l}$ of a two-prover game $\mathcal{G}$ is a game in which the two provers are sent random sets of questions from $\mathc…