Soundness bounds for multi-answer birthday graphs in constraint problems

Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

Computational ComplexityData Structures and Algorithms

Summary

This paper studies a kind of mathematical graph used to represent partial solutions in complex logical puzzles involving many variables. The authors found new ways to measure how closely these partial solutions resemble a perfect complete solution, even when the data overlaps or repeats unpredictably. Their results improve previous bounds on how hard it is to find truly sound solutions under these conditions. They also provide a related result showing stability properties for sets of partial solutions with missing or multiple answers. However, the work does not establish new hardness results for computational problems.

What this means in practice

  • For constraint solver developers: Use refined soundness bounds to better evaluate solution reliability in constraint satisfaction solvers working with overlapping partial assignments.
  • For complexity theorists: Guide approach to proving computational hardness or stability properties in related bounded-occurrence boolean CSPs with multiple answers per query.

A theory result. No direct application yet.

Authors

Alexandru Popa

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=\binom n\ell$, 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_0n$ 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_*(H)\le34(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.