Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

arXiv:2611.04457 · cs.CC, cs.DS · Submitted 2026-11-03 · Read on arXiv

cs.CC, cs.DS

Submitted: 2026-11-03

Updated: 2026-11-03

Comments: 29 pages

License: http://creativecommons.org/licenses/by/4.0/

The gist: The vertices of a Boolean birthday graph are partial assignments on-subsets of n variables.

Terminology

Abstract

The vertices of a Boolean birthday graph are partial assignments on-subsets of n variables. Although a satisfying assignment induces a K-clique for K= n, 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) at most 2 ! (-c, cubed over n 2 (en/))] for 2 at most at most x 0n and (en/) at least C 0 (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*(H) at most34(n/)q con(H) for every 1 at most at most n. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

Sources

Related papers