:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Li, Qian, Wang, Yuyi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Machine Learning
Online-Zugang:	https://arxiv.org/abs/2506.12027
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Efficient Turing Machine Simulation with Transformers
von: Li, Qian, et al.
Veröffentlicht: (2025)

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

On the Expressive Power and Limitations of Multi-Layer SSMs
von: Zubić, Nikola, et al.
Veröffentlicht: (2026)

Ask, and it shall be given: On the Turing completeness of prompting
von: Qiu, Ruizhong, et al.
Veröffentlicht: (2024)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
von: Liu, Yuxi
Veröffentlicht: (2025)

New Hardness Results for Low-Rank Matrix Completion
von: Chawin, Dror, et al.
Veröffentlicht: (2025)

Flat origami is Turing Complete
von: Hull, Thomas C., et al.
Veröffentlicht: (2023)

Infinite Time Turing Machines and their Applications
von: Weerawarana, Rukmal, et al.
Veröffentlicht: (2025)

Unlocking the Theory Behind Scaling 1-Bit Neural Networks
von: Daliri, Majid, et al.
Veröffentlicht: (2024)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
von: Li, Zhiyuan, et al.
Veröffentlicht: (2024)

On the Computational Hardness of Transformers
von: Saha, Barna, et al.
Veröffentlicht: (2026)

A Logic for Expressing Log-Precision Transformers
von: Merrill, William, et al.
Veröffentlicht: (2022)

Turing Completeness and Sid Meier's Civilization
von: de Wynter, Adrian
Veröffentlicht: (2021)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
von: Amiri, Alireza, et al.
Veröffentlicht: (2025)

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

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

Fundamental Limitations on Subquadratic Alternatives to Transformers
von: Alman, Josh, et al.
Veröffentlicht: (2024)

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
von: Wang, Xiao
Veröffentlicht: (2026)

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

Provably Overwhelming Transformer Models with Designed Inputs
von: Stambler, Lev, et al.
Veröffentlicht: (2025)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
von: Chen, Bo, et al.
Veröffentlicht: (2024)

No Complete Problem for Constant-Cost Randomized Communication
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
von: Wang, Jie, et al.
Veröffentlicht: (2024)

Certifiable Boolean Reasoning Is Universal
von: Li, Wenhao, et al.
Veröffentlicht: (2026)

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

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

Learning Tree Pattern Transformations
von: Neider, Daniel, et al.
Veröffentlicht: (2024)

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

Polyhedral Instability Governs Regret in Online Learning
von: Li, Yuetai, et al.
Veröffentlicht: (2026)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
von: Huang, Zekai, et al.
Veröffentlicht: (2025)

The Expressive Power of Transformers with Chain of Thought
von: Merrill, William, et al.
Veröffentlicht: (2023)

On the Hardness of Learning Regular Expressions
von: Attias, Idan, et al.
Veröffentlicht: (2025)

Low-Rank Matrix Approximation for Neural Network Compression
von: Cherukuri, Kalyan, et al.
Veröffentlicht: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
von: Cao, Yang, et al.
Veröffentlicht: (2025)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
von: Huang, Jizhou, et al.
Veröffentlicht: (2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
von: Rohatgi, Dhruv, et al.
Veröffentlicht: (2025)

How Global Calibration Strengthens Multiaccuracy
von: Casacuberta, Sílvia, et al.
Veröffentlicht: (2025)

Diffusion Language Models are Provably Optimal Parallel Samplers
von: Jiang, Haozhe, et al.
Veröffentlicht: (2025)

Additive Models Explained: A Computational Complexity Approach
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
von: Kou, Yiwen, et al.
Veröffentlicht: (2025)