Cover Image

The Limits of Tractable Marginalization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Broadrick, Oliver, Agarwal, Sanyam, Broeck, Guy Van den, Bläser, Markus
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Probabilistic Generating Circuits -- Demystified
by: Agarwal, Sanyam, et al.
Published: (2024)

Polynomial Semantics of Tractable Probabilistic Circuits
by: Broadrick, Oliver, et al.
Published: (2024)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
by: Agarwal, Sanyam, et al.
Published: (2026)

Learning Tractable Distributions Of Language Model Continuations
by: Yidou-Weng, Gwen, et al.
Published: (2025)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
by: Dörfler, Julian, et al.
Published: (2024)

On the Complexity of Identification in Linear Structural Causal Models
by: Dörfler, Julian, et al.
Published: (2024)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
by: Ganian, Robert, et al.
Published: (2025)

Probabilistic and Causal Satisfiability: Constraining the Model
by: Bläser, Markus, et al.
Published: (2025)

Probabilistic Circuits for Cumulative Distribution Functions
by: Broadrick, Oliver, et al.
Published: (2024)

Restructuring Tractable Probabilistic Circuits
by: Zhang, Honghua, et al.
Published: (2024)

A Tractable Inference Perspective of Offline RL
by: Liu, Xuejie, et al.
Published: (2023)

The Complexity of Symmetry Breaking Beyond Lex-Leader
by: Anders, Markus, et al.
Published: (2024)

How to Marginalize in Causal Structure Learning?
by: Zhao, William, et al.
Published: (2025)

Structure-Aware Encodings of Argumentation Properties for Clique-width
by: Mahmood, Yasir, et al.
Published: (2025)

Diversity of Extensions in Abstract Argumentation
by: Fichte, Johannes K., et al.
Published: (2026)

Limitations on Accurate, Trusted, Human-level Reasoning
by: Panigrahy, Rina, et al.
Published: (2025)

On the Expressive Power and Limitations of Multi-Layer SSMs
by: Zubić, Nikola, et al.
Published: (2026)

Partial Evidence Bench: Benchmarking Authorization-Limited Evidence in Agentic Systems
by: Tallam, Krti
Published: (2026)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

Rejection in Abstract Argumentation: Harder Than Acceptance?
by: Fichte, Johannes K., et al.
Published: (2024)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
by: Zhang, Yuyang, et al.
Published: (2026)

On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning
by: Lyu, Siyi, et al.
Published: (2026)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
by: Chen, Yifang, et al.
Published: (2024)

Forgetting in short and heterogeneous sequences of belief revisions
by: Liberatore, Paolo
Published: (2025)

Value Iteration with Guessing for Markov Chains and Markov Decision Processes
by: Chatterjee, Krishnendu, et al.
Published: (2025)

On the Holographic Geometry of Deterministic Computation
by: Nye, Logan
Published: (2025)

Complexity Results of Persuasion
by: Grastien, Alban
Published: (2025)

Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations
by: Liu, Shaoshan, et al.
Published: (2025)

A Quantale-Weakness Route to $P \neq NP$ via CD Evidence Normalization and Gauge-Buffered Locked Ensembles
by: Goertzel, Ben
Published: (2025)

Solving Multiagent Path Finding on Highly Centralized Networks
by: Fioravantes, Foivos, et al.
Published: (2024)

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
by: Asadi, Ali, et al.
Published: (2026)

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
by: Eriksson, Leif, et al.
Published: (2026)

Over the Edge of Chaos? Excess Complexity as a Roadblock to Artificial General Intelligence
by: Susnjak, Teo, et al.
Published: (2024)

CSPs with Few Alien Constraints
by: Jonsson, Peter, et al.
Published: (2024)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
by: Goertzel, Ben, et al.
Published: (2026)

The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
by: Lu, Chien-Ping
Published: (2026)

Parameterized Complexity Of Representing Models Of MSO Formulas
by: Kučera, Petr, et al.
Published: (2026)

An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages
by: Fargier, Hélène, et al.
Published: (2021)