Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

Abstract

The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le \ell \le x_{0}n$ and $\ell \log (en/\ell )\ge C_0\log (n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_{\ast }(H)\le 34(n/\ell )q_{\mathrm{con}}(H)$ for every $1\le \ell \le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

arXiv comment29 pages