Copertina

A Logic for Expressing Log-Precision Transformers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Merrill, William, Sabharwal, Ashish
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Machine Learning Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
di: Merrill, William, et al.
Pubblicazione: (2025)

The Expressive Power of Transformers with Chain of Thought
di: Merrill, William, et al.
Pubblicazione: (2023)

Exact Expressive Power of Transformers with Padding
di: Merrill, William, et al.
Pubblicazione: (2025)

The Illusion of State in State-Space Models
di: Merrill, William, et al.
Pubblicazione: (2024)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
di: Svete, Anej, et al.
Pubblicazione: (2026)

Why Are Linear RNNs More Parallelizable?
di: Merrill, William, et al.
Pubblicazione: (2026)

Context-Free Recognition with Transformers
di: Jerad, Selim, et al.
Pubblicazione: (2026)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
di: Brösamle, Moritz, et al.
Pubblicazione: (2026)

On the Computational Hardness of Transformers
di: Saha, Barna, et al.
Pubblicazione: (2026)

Constant Bit-size Transformers Are Turing Complete
di: Li, Qian, et al.
Pubblicazione: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
di: Amiri, Alireza, et al.
Pubblicazione: (2025)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
di: Li, Zhiyuan, et al.
Pubblicazione: (2024)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
di: Li, Qian, et al.
Pubblicazione: (2026)

Fundamental Limitations on Subquadratic Alternatives to Transformers
di: Alman, Josh, et al.
Pubblicazione: (2024)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
di: Chen, Bo, et al.
Pubblicazione: (2025)

Provably Overwhelming Transformer Models with Designed Inputs
di: Stambler, Lev, et al.
Pubblicazione: (2025)

Additive Models Explained: A Computational Complexity Approach
di: Bassan, Shahaf, et al.
Pubblicazione: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
di: Cao, Yang, et al.
Pubblicazione: (2025)

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

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
di: Wang, Xiao
Pubblicazione: (2026)

Learning Tree Pattern Transformations
di: Neider, Daniel, et al.
Pubblicazione: (2024)

Efficient Turing Machine Simulation with Transformers
di: Li, Qian, et al.
Pubblicazione: (2025)

Reachability In Simple Neural Networks
di: Sälzer, Marco, et al.
Pubblicazione: (2022)

On the Hardness of Learning Regular Expressions
di: Attias, Idan, et al.
Pubblicazione: (2025)

Learnability of Parameter-Bounded Bayes Nets
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2024)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
di: Majumdar, Angshul
Pubblicazione: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
di: Cherukuri, Kalyan, et al.
Pubblicazione: (2025)

Proximity to Losslessly Compressible Parameters
di: Farrugia-Roberts, Matthew
Pubblicazione: (2023)

Decision Tree Learning on Product Spaces
di: Moakahr, Arshia Soltani, et al.
Pubblicazione: (2026)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
di: Wang, Jie, et al.
Pubblicazione: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
di: Chandrasekaran, Gautam, et al.
Pubblicazione: (2024)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
di: Jacobs, Peter Matthew, et al.
Pubblicazione: (2026)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
di: Huang, Jizhou, et al.
Pubblicazione: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
di: Dwork, Cynthia, et al.
Pubblicazione: (2023)

Ask, and it shall be given: On the Turing completeness of prompting
di: Qiu, Ruizhong, et al.
Pubblicazione: (2024)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
di: Rohatgi, Dhruv, et al.
Pubblicazione: (2025)

How Global Calibration Strengthens Multiaccuracy
di: Casacuberta, Sílvia, et al.
Pubblicazione: (2025)

Diffusion Language Models are Provably Optimal Parallel Samplers
di: Jiang, Haozhe, et al.
Pubblicazione: (2025)

Certifiable Boolean Reasoning Is Universal
di: Li, Wenhao, et al.
Pubblicazione: (2026)