Entropy-Weighted Soundness for Multi-Answer Birthday Graphs
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
- ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
- Almost-Polynomial Ratio Almost-ETH-Hardness of Approximating Densest k-Subgraph
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?