Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Hardness of Approximating Distributions with Tractable Probabilistic Models
Authors: John Leland, YooJung Choi
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contributions are as follows: (1) we prove that it is NP-hard to approximate distributions within a bounded f-divergence using any model that supports tractable marginals, with proof via a reduction from SAT (Theorem 3.4 and 3.5); (2) we derive an unconditional, exponential separation between decomposable PCs and decomposable & deterministic PCs for approximate modeling (Theorem 4.1); (3) we study the relationship between bounds on divergence measures for approximate modeling and approximation errors for marginal and maximum-a-posteriori (MAP) inference, characterizing when one is or is not sufficient to guarantee the other (Sections 3.1 and 5). |
| Researcher Affiliation | Academia | John Leland Yoo Jung Choi School of Computing and Augmented Intelligence Arizona State University EMAIL, EMAIL |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. Algorithm steps are described in narrative form, for example, in Appendix A.3.2: 'We describe our pruning algorithm below. First, we collect the an upper bound on each edge...' |
| Open Source Code | No | The paper does not contain any statements regarding the release of open-source code nor provides links to code repositories. The NeurIPS Paper Checklist also indicates 'NA' for experimental result reproducibility and open access to data and code, suggesting no code was provided. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets. It discusses theoretical constructs like 'distributions' and the 'Sauerhoff function' for proofs, but does not use or provide access information for any publicly available or open datasets for empirical validation. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments that would require dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or system-level training settings. |