Buchumschlag

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chernobrovkin, Artem, Sälzer, Marco, Schwarzentruber, François, Troquard, Nicolas
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Logic in Computer Science Artificial Intelligence Computational Complexity Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Verifying Quantized Graph Neural Networks is PSPACE-complete
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
von: Nunn, Pierre, et al.
Veröffentlicht: (2024)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
von: Sälzer, Marco, et al.
Veröffentlicht: (2024)

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
von: Alsmann, Eric, et al.
Veröffentlicht: (2026)

Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
von: Ghosh, Avijeet, et al.
Veröffentlicht: (2025)

Lecture Notes on Verifying Graph Neural Networks
von: Schwarzentruber, François
Veröffentlicht: (2025)

The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

Towards Understanding the Expressive Power of GNNs with Global Readout
von: Funk, Maurice, et al.
Veröffentlicht: (2026)

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
von: Artale, Alessandro, et al.
Veröffentlicht: (2025)

The Computational Complexity of Satisfiability in State Space Models
von: Alsmann, Eric, et al.
Veröffentlicht: (2025)

On Probabilistic and Causal Reasoning with Summation Operators
von: Ibeling, Duligur, et al.
Veröffentlicht: (2024)

Halting Recurrent GNNs and the Graded $μ$-Calculus
von: Bollen, Jeroen, et al.
Veröffentlicht: (2025)

Testing for Renamability to Classes of Clause Sets
von: Brandl, Albert, et al.
Veröffentlicht: (2025)

Measuring Decidability as Related to Busy Beaver Numbers
von: Tandi, Gurpreet, et al.
Veröffentlicht: (2026)

Epistemic Skills: Reasoning about Knowledge and Oblivion
von: Liang, Xiaolong, et al.
Veröffentlicht: (2025)

Complexity of Faceted Explanations in Propositional Abduction
von: Schmidt, Johannes, et al.
Veröffentlicht: (2025)

Epistemic Logic Programs: Non-Ground and Counting Complexity
von: Eiter, Thomas, et al.
Veröffentlicht: (2025)

Probabilistic and Causal Satisfiability: Constraining the Model
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

Minimal Model Reasoning in Description Logics: Don't Try This at Home!
von: Di Stefano, Federica, et al.
Veröffentlicht: (2025)

Compilation and Fast Model Counting beyond CNF
von: de Colnet, Alexis, et al.
Veröffentlicht: (2025)

Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
von: Li, Jinzhao, et al.
Veröffentlicht: (2023)

A Theory of Formalisms for Representing Knowledge
von: Zhang, Heng, et al.
Veröffentlicht: (2024)

Data Complexity in Expressive Description Logics With Path Expressions
von: Bednarczyk, Bartosz
Veröffentlicht: (2024)

Rejection in Abstract Argumentation: Harder Than Acceptance?
von: Fichte, Johannes K., et al.
Veröffentlicht: (2024)

Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
von: Wilson, Nic, et al.
Veröffentlicht: (2024)

Spectra of Cardinality Queries over Description Logic Knowledge Bases
von: Manière, Quentin, et al.
Veröffentlicht: (2024)

A Computationally Grounded Framework for Cognitive Attitudes (extended version)
von: de Lima, Tiago, et al.
Veröffentlicht: (2024)

On the Computational Tractability of the (Many) Shapley Values
von: Marzouk, Reda, et al.
Veröffentlicht: (2025)

What makes an Ensemble (Un) Interpretable?
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)

The Descriptive Complexity of Graph Neural Networks
von: Grohe, Martin
Veröffentlicht: (2023)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
von: Amir, Guy, et al.
Veröffentlicht: (2024)

Provably Explaining Neural Additive Models
von: Bassan, Shahaf, et al.
Veröffentlicht: (2026)

Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
von: Khalife, Sammy, et al.
Veröffentlicht: (2024)

Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
von: Zubić, Nikola, et al.
Veröffentlicht: (2024)

Can Transformers Learn to Verify During Backtracking Search?
von: Phua, Yin Jun, et al.
Veröffentlicht: (2026)

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs
von: Pati, Viresh, et al.
Veröffentlicht: (2026)

Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks
von: Boetius, David, et al.
Veröffentlicht: (2026)

Decidable By Construction: Design-Time Verification for Trustworthy AI
von: Haynes, Houston
Veröffentlicht: (2026)

SATQuest: A Verifier for Logical Reasoning Evaluation and Reinforcement Fine-Tuning of LLMs
von: Zhao, Yanxiao, et al.
Veröffentlicht: (2025)