Cover Image

On the Complexity of Neural Computation in Superposition

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adler, Micah, Shavit, Nir
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Artificial Intelligence Data Structures and Algorithms Neural and Evolutionary Computing F.1.1; F.2.2; I.2.m; E.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

Abstraction in Neural Networks
by: Lynch, Nancy
Published: (2024)

An Efficient Algorithm for Unbalanced 1D Transportation
by: Gouvine, Gabriel
Published: (2023)

Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction
by: Arcas, Blaise Agüera y, et al.
Published: (2024)

When Votes Change and Committees Should (Not)
by: Bredereck, Robert, et al.
Published: (2020)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

Identity Testing for Circuits with Exponentiation Gates
by: Li, Jiatu, et al.
Published: (2025)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

The Chonkers Algorithm: Content-Defined Chunking with Provable Strict Guarantees on Size and Locality
by: Berger, Benjamin
Published: (2025)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Line Cover and Related Problems
by: Bentert, Matthias, et al.
Published: (2025)

Optimal Preprocessing for Answering On-Line Product Queries
by: Alon, Noga, et al.
Published: (2024)

Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores
by: Garg, Ishant
Published: (2026)

Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
by: Brodal, Gerth Stølting
Published: (2024)

Eliminating Illusion in Directed Networks
by: Jana, Sougata, et al.
Published: (2026)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

Average Attention Transformers and Arithmetic Circuits
by: Ehrmuth, Lena, et al.
Published: (2026)

Towards Combinatorial Interpretability of Neural Computation
by: Adler, Micah, et al.
Published: (2025)

Min-CSPs on Complete Instances
by: Anand, Aditya, et al.
Published: (2024)

An island-parallel ensemble metaheuristic algorithm for large graph coloring problems
by: Dokeroglu, Tansel, et al.
Published: (2025)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

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

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

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

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

Anyone but Him: The Complexity of Precluding an Alternative
by: Hemaspaandra, Edith, et al.
Published: (2005)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
by: Schmitz, Sylvain, et al.
Published: (2023)