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

Inapproximability results for $\mathsf{M}\mathsf{a}\mathsf{x}\mathsf{k}\mathsf{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\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{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\mathsf{q}$, providing new structural insights and approximation bounds. We first establish a direct connection between the average differential ratio on $\mathsf{k}\mathsf{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\mathsf{q}$ instances and orthogonal arrays. This allows us to derive the new differential approximability bounds of $1\mathrm{/}{q}^k$ for $(k+1)$-partite instances, $\mathrm{\Omega }(1\mathrm{/}{n}^{\lfloor k\mathrm{/}2\rfloor })$ for Boolean instances, $\mathrm{\Omega }(1\mathrm{/}n)$ when $k=2$, and $\mathrm{\Omega }(1\mathrm{/}{n}^{k-\lceil {\log }_{\mathrm{\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{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\mathsf{q}$ to $\mathsf{k}\mathsf{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\mathsf{k}$ (where $q>k$), with an expansion factor of $1\mathrm{/}(q-k\mathrm{/}2{)}^k$ on the differential approximation guarantee. Combining this with a 1998 result by Yuri Nesterov, we conclude that $\mathsf{2}\mathsf{C}\mathsf{S}\mathsf{P}\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}\mathsf{q}$ is approximable within a differential factor of $0.429\mathrm{/}(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 $\mathrm{\Omega }(1\mathrm{/}{n}^k)$-approximation of the instance diameter. Thus, our work highlights the relevance of combinatorial designs for establishing structural differential approximation guarantees for CSPs.