Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

Alexandru Popa

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…