Research map / Learning theory and algorithms / Sample complexity
Probabilistic Generating Circuits - Demystified
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that probabilistic generating circuits (PGCs) are probabilistic circuits with negative weights in disguise, and proves that PGCs over categorical variables with more than two values cannot support tractable marginalization unless NP = DP.
Problem
Understanding what gives probabilistic generating circuits (PGCs) their extra expressive power over probabilistic circuits (PCs) and determinantal point processes (DPPs), and whether PGCs support tractable marginalization for non-binary categorical variables.
Approach
Any PGC over binary variables can be transformed into a nonmonotone PC (with negative weights) computing the same distribution with polynomial overhead, so the power comes from negative weights rather than the generating-polynomial representation; for larger domains, nonmonotone PCs computing set-multilinear polynomials support tractable marginalization where PGCs do not.
Key results
- Every PGC over binary variables can be simulated by a nonmonotone PC with polynomial overhead in size (Strassen-style construction).
- Efficient marginalization over PGCs with quaternary variables would imply #P = FP, hence NP = DP (reduction from counting perfect matchings in 3-regular bipartite graphs).
- Every arithmetic formula can be written as an affine projection of a DPP, and ABPs can be represented as DPPs of polynomial size.
Surprising findings
- Testing whether a nonmonotone PC computes a probability distribution is NP-hard, while testing set-multilinearity is doable in randomized polynomial time.
Limitations
- Does not resolve whether PGCs over ternary variables support full (non-selective) tractable marginalization
- Hardness results rely on complexity assumptions (NP != DP)
- Nonmonotone PCs lack a tractable check for being a probability distribution
Experimental setup
Baselines: probabilistic circuits determinantal point processes probabilistic generating circuits
Builds on: probabilistic generating circuits probabilistic circuits determinantal point processes
Closest papers by meaning
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.83)
- On the Relationship Between Monotone and Squared Probabilistic Circuits (AAAI 2025 · similarity 0.83)
- Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.82)
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.81)
- Probabilistic Neural Circuits (AAAI 2024 · similarity 0.81)
- Scaling Tractable Probabilistic Circuits: A Systems Perspective (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.