Buchumschlag

Average Attention Transformers and Arithmetic Circuits

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ehrmuth, Lena, Strieker, Laura
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Artificial Intelligence Machine Learning F.1.1; F.1.3; I.2.m
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2026)

Explicit Commutative ROABPs from Partial Derivatives
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2024)

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
von: Bajaj, Divya, et al.
Veröffentlicht: (2026)

Catalytic Computing and Register Programs Beyond Log-Depth
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

A point to set principle for finite-state dimension
von: Mayordomo, Elvira
Veröffentlicht: (2022)

On the Complexity of Neural Computation in Superposition
von: Adler, Micah, et al.
Veröffentlicht: (2024)

Imperative process algebra and models of computation
von: Middelburg, C. A.
Veröffentlicht: (2022)

Realizable Circuit Complexity: Embedding Computation in Space-Time
von: Prada, Benjamin, et al.
Veröffentlicht: (2025)

Symmetric Arithmetic Circuits
von: Dawar, Anuj, et al.
Veröffentlicht: (2020)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

On bounded depth proofs for Tseitin formulas on the grid; revisited
von: Håstad, Johan, et al.
Veröffentlicht: (2022)

The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems
von: Guo, Dongxin
Veröffentlicht: (2026)

Does GPT Really Get It? A Hierarchical Scale to Quantify Human vs AI's Understanding of Algorithms
von: Reid, Mirabel, et al.
Veröffentlicht: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2019)

The Serial Scaling Hypothesis
von: Liu, Yuxi, et al.
Veröffentlicht: (2025)

On the Counting Complexity of the Skolem Problem
von: Jindal, Gorav, et al.
Veröffentlicht: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
von: Antonelli, Melissa, et al.
Veröffentlicht: (2025)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

Arithmetic Complexity of Solutions of the Dirichlet Problem
von: Boche, Holger, et al.
Veröffentlicht: (2026)

Towards a Neural Lambda Calculus: Neurosymbolic AI Applied to the Foundations of Functional Programming
von: Flach, João, et al.
Veröffentlicht: (2023)

Search versus Search for Collapsing Electoral Control Types
von: Carleton, Benjamin, et al.
Veröffentlicht: (2022)

Anyone but Him: The Complexity of Precluding an Alternative
von: Hemaspaandra, Edith, et al.
Veröffentlicht: (2005)

Tight bounds on depth-2 QAC-circuits computing parity
von: Fenner, Stephen, et al.
Veröffentlicht: (2025)

$\rm P$ has polynomial-time finite-state verifiers
von: Gezer, M. Utkan, et al.
Veröffentlicht: (2023)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
von: Anand, Emile, et al.
Veröffentlicht: (2024)

Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
von: Ahvonen, Veeti, et al.
Veröffentlicht: (2026)

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
von: Makowski, Michał
Veröffentlicht: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
von: Ducloz, Gwendal, et al.
Veröffentlicht: (2025)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
von: Kawałek, Piotr, et al.
Veröffentlicht: (2026)

Lower Bounds for Symmetric Circuits for the Determinant
von: Dawar, Anuj, et al.
Veröffentlicht: (2021)

Federated Learning: From Theory to Practice
von: Jung, A.
Veröffentlicht: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
von: Pavlov, Gorgi
Veröffentlicht: (2026)

Multidimensional Adaptive Coefficient for Inference Trajectory Optimization in Flow and Diffusion
von: Lee, Dohoon, et al.
Veröffentlicht: (2024)

Graph-Based Deterministic Polynomial Framwork for NP Problems
von: Lee, Changryeol
Veröffentlicht: (2025)