Deriving differential approximation results for $k$CSPs from combinatorial designs

Abstract

Inapproximability results for $\mathsf{Max}\mathsf{k}\mathsf{CSP}-\mathsf{q}$ have been traditionally established using balanced $t$-wise independent distributions, which are closely related to orthogonal arrays, a famous family of combinatorial designs. In this work, we investigate the role of these combinatorial structures in the context of the differential approximability of $\mathsf{k}\mathsf{CSP}-\mathsf{q}$, providing new structural insights and approximation bounds. We first establish a direct connection between the average differential ratio on $\mathsf{k}\mathsf{CSP}-\mathsf{q}$ instances and orthogonal arrays. This allows us to derive the new differential approximability bounds of $1/q^k$ for $(k+1)$-partite instances, $\Omega (1/n^{\lfloor k/2\rfloor })$ for Boolean instances, $\Omega (1/n)$ when $k=2$, and $\Omega (1/n^{k-\lceil {\log }_{\Theta (q)}k\rceil })$ when $k,q\ge 3$. We then introduce families of array pairs, called {\em alphabet reduction pairs of arrays}, that are still related to balanced $k$-wise independence. Using these pairs of arrays, we establish a reduction from $\mathsf{k}\mathsf{CSP}-\mathsf{q}$ to $\mathsf{k}\mathsf{CSP}-\mathsf{k}$ (where $q>k$), with an expansion factor of $1/(q-k/2{)}^k$ on the differential approximation guarantee. Combining this with a 1998 result by Yuri Nesterov, we conclude that $2\mathsf{CSP}-\mathsf{q}$ is approximable within a differential factor of $0.429/(q-1{)}^2$. Finally, using similar Boolean array pairs, {\em called cover pairs of arrays}, we prove that every Hamming ball of radius $k$ provides a $\Omega (1/n^k)$-approximation of the instance diameter. Thus, our work highlights the relevance of combinatorial designs for establishing structural differential approximation guarantees for CSPs.

Preliminary versions of this work have been presented or published at the ISCO 2012, ISCO 2018 and IWOCA 2018 conferences