Metraipolis › archive › dc_300d12ed2d91
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures — arXiv:2611.02346
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02346
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:46:31.567Z
- SHA-256 of the archived text
1b22b50e397b9132d5735a1f3187f0905e4a80a59658e5cb7dbc94f65a27c903- Stable URL of this page
https://metraipolis.com/documento/dc_300d12ed2d91
How to cite
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures — arXiv:2611.02346 — arXiv (en), https://arxiv.org/abs/2611.02346 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_300d12ed2d91 (Metraipolis archive dc_300d12ed2d91, sha256 1b22b50e397b9132d5735a1f3187f0905e4a80a59658e5cb7dbc94f65a27c903)
BibTeX
@misc{dc300d12ed2d91,
title = {Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures — arXiv:2611.02346},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02346},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_300d12ed2d91; sha256 1b22b50e397b9132d5735a1f3187f0905e4a80a59658e5cb7dbc94f65a27c903},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02346. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Score-based generative models rely on access to accurate scores, but the cost of computing those scores depends on how the underlying distribution is represented. Can smoothness and strong log-concavity make score evaluation efficient when a distribution is specified by Boolean constraints? I investigate this question by separating geometric encoding from computational extraction. I construct a succinctly specified Gaussian mixture whose score at a fixed query location encodes whether a Boolean formula is satisfiable. The construction has rational component means and uniform strong log-concavity, yet deterministic polynomial-time approximation of the designated score coordinate to constant absolute accuracy is equivalent to polynomial-time solvability of Boolean satisfiability. This equivalence remains valid throughout a neighborhood whose radius is independent of dimension. I further characterize how numerical precision connects bounded witness enumeration to exact counting, and show that independent sample access turns the same target into a dimension-independent mean-estimation problem. An explicit parity construction also separates low-degree approximation from efficient computation. Together, these results show that favorable geometry alone does not resolve the computational cost of extracting scores from compact descriptions. They identify the precise extraction requirement in this formulation while leaving the existence of a general efficient evaluator open. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2611.02346 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T11:08:22.219Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).