On Relaxing Determinism in Arithmetic Circuits
Not on the map. Why?
Abstract (arXiv)
The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).
Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Aug 2017.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 3; 2022: 4; 2023: 1; 2024: 4; 2025: 2.
14 papers.
Sort:
By area:
- 2024R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoningcited by 43
- 2021Tractable Regularization of Probabilistic Circuitscited by 39
- 2022Tractable Uncertainty for Structure Learningcited by 15
- 2022Causal Inference Using Tractable Circuitscited by 12
- 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Modelscited by 10
- 2022Tractable Boolean and Arithmetic Circuitscited by 9
- 2024COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuitscited by 9
- 2021Provable Guarantees on the Robustness of Decision Rules to Causal Interventionscited by 6
- 2022Certifying Fairness of Probabilistic Circuitscited by 3
- 2024Causal Unit Selection using Tractable Arithmetic Circuitscited by 3
- 2025On the Hardness of Approximating Distributions with Tractable Probabilistic Modelscited by 2
- 2021Explaining Deep Tractable Probabilistic Models: The sum-product network casecited by 1
- 2025Hardware-efficient tractable probabilistic inference for TinyML Neurosymbolic AI applications7 Jul 2025
- 2025On the Hardness of Approximating Distributions with Tractable Probabilistic Models2 Jun 2025
- 2024Optimal Transport for Probabilistic Circuits16 Oct 2024
- 2024R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoning8 Jul 2024
- 2024Causal Unit Selection using Tractable Arithmetic Circuits10 Apr 2024
- 2024COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits17 Mar 2024
- 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Models17 Apr 2023
- 2022Certifying Fairness of Probabilistic Circuits5 Dec 2022
- 2022Tractable Uncertainty for Structure Learning29 Apr 2022
- 2022Tractable Boolean and Arithmetic Circuits7 Feb 2022
- 2022Causal Inference Using Tractable Circuits7 Feb 2022
- 2021Explaining Deep Tractable Probabilistic Models: The sum-product network case19 Oct 2021
2 more
- 2021Tractable Regularization of Probabilistic Circuitscited by 39
- 2022Tractable Uncertainty for Structure Learningcited by 15
- 2022Causal Inference Using Tractable Circuitscited by 12
- 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Modelscited by 10
- 2022Tractable Boolean and Arithmetic Circuitscited by 9
- 2024COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuitscited by 9
- 2021Provable Guarantees on the Robustness of Decision Rules to Causal Interventionscited by 6
- 2022Certifying Fairness of Probabilistic Circuitscited by 3
- 2024Causal Unit Selection using Tractable Arithmetic Circuitscited by 3
- 2025On the Hardness of Approximating Distributions with Tractable Probabilistic Modelscited by 2
- 2021Explaining Deep Tractable Probabilistic Models: The sum-product network casecited by 1
- 2024Optimal Transport for Probabilistic Circuitscited by 1
12 most cited of 13 All 13 (JSON)
- 2025Hardware-efficient tractable probabilistic inference for TinyML Neurosymbolic AI applications7 Jul 2025
- 2025On the Hardness of Approximating Distributions with Tractable Probabilistic Models2 Jun 2025
- 2024Optimal Transport for Probabilistic Circuits16 Oct 2024
- 2024Causal Unit Selection using Tractable Arithmetic Circuits10 Apr 2024
- 2024COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits17 Mar 2024
- 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Models17 Apr 2023
- 2022Certifying Fairness of Probabilistic Circuits5 Dec 2022
- 2022Tractable Uncertainty for Structure Learning29 Apr 2022
- 2022Tractable Boolean and Arithmetic Circuits7 Feb 2022
- 2022Causal Inference Using Tractable Circuits7 Feb 2022
- 2021Explaining Deep Tractable Probabilistic Models: The sum-product network case19 Oct 2021
- 2021Tractable Regularization of Probabilistic Circuits4 Jun 2021
12 newest of 13 All 13 (JSON)