Copertina

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Qian, Mao, Xinyu, Teng, Shang-Hua
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Machine Learning Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Circuit Complexity Bounds for RoPE-based Transformer Architecture
di: Chen, Bo, et al.
Pubblicazione: (2024)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
di: Liu, Yuxi
Pubblicazione: (2025)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
di: Li, Xiaoyu, et al.
Pubblicazione: (2024)

New Hardness Results for Low-Rank Matrix Completion
di: Chawin, Dror, et al.
Pubblicazione: (2025)

Flat origami is Turing Complete
di: Hull, Thomas C., et al.
Pubblicazione: (2023)

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

Transductive Learning Is Compact
di: Asilis, Julian, et al.
Pubblicazione: (2024)

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

RoPE Attention Can Be Trained in Almost Linear Time
di: Cao, Yang, et al.
Pubblicazione: (2024)

A Logic for Expressing Log-Precision Transformers
di: Merrill, William, et al.
Pubblicazione: (2022)

Infinite Time Turing Machines and their Applications
di: Weerawarana, Rukmal, et al.
Pubblicazione: (2025)

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

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
di: Zhang, Zhihan, et al.
Pubblicazione: (2024)

Turing Completeness and Sid Meier's Civilization
di: de Wynter, Adrian
Pubblicazione: (2021)

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

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
di: Bertschinger, Daniel, et al.
Pubblicazione: (2022)

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

Oblivious Defense in ML Models: Backdoor Removal without Detection
di: Goldwasser, Shafi, et al.
Pubblicazione: (2024)

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

SeqPE: Transformer with Sequential Position Encoding
di: Li, Huayang, et al.
Pubblicazione: (2025)

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

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

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

Polyhedral Instability Governs Regret in Online Learning
di: Li, Yuetai, et al.
Pubblicazione: (2026)

Low degree conjecture implies sharp computational thresholds in stochastic block model
di: Ding, Jingqiu, 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)

Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
di: Chen, Yifang, et al.
Pubblicazione: (2025)

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

NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
di: Fan, Lizhou, et al.
Pubblicazione: (2023)

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)

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

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

Hidden costs for inference with deep network on embedded system devices
di: Lee, Chankyu, et al.
Pubblicazione: (2026)

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
di: Klivans, Adam R., et al.
Pubblicazione: (2026)

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