The Limits of Tractable Marginalization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916843545952256 |
|---|---|
| author | Broadrick, Oliver Agarwal, Sanyam Broeck, Guy Van den Bläser, Markus |
| author_facet | Broadrick, Oliver Agarwal, Sanyam Broeck, Guy Van den Bläser, Markus |
| contents | Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can be commonly expressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\textsf{FP}\neq\#\textsf{P}$ (an assumption implied by $\textsf{P} \neq \textsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Limits of Tractable Marginalization Broadrick, Oliver Agarwal, Sanyam Broeck, Guy Van den Bläser, Markus Computational Complexity Artificial Intelligence Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can be commonly expressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\textsf{FP}\neq\#\textsf{P}$ (an assumption implied by $\textsf{P} \neq \textsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation. |
| title | The Limits of Tractable Marginalization |
| topic | Computational Complexity Artificial Intelligence |
| url | https://arxiv.org/abs/2506.12020 |