Buchumschlag

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Liu, Yuxi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Computation and Language Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Transformers in Uniform TC$^0$
von: Chiang, David
Veröffentlicht: (2024)

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

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
von: Cao, Yang, et al.
Veröffentlicht: (2024)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
von: Grier, Daniel, et al.
Veröffentlicht: (2026)

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

Constant Bit-size Transformers Are Turing Complete
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 Efficiently Representing Regular Languages as RNNs
von: Svete, Anej, et al.
Veröffentlicht: (2024)

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

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
von: AbdElhameed, Marwan, et al.
Veröffentlicht: (2024)

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

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
von: Göller, Stefan, et al.
Veröffentlicht: (2023)

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

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

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

Circuit Complexity Bounds for Visual Autoregressive Model
von: Ke, Yekun, et al.
Veröffentlicht: (2025)

RoPE Attention Can Be Trained in Almost Linear Time
von: Cao, Yang, et al.
Veröffentlicht: (2024)

A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
von: Zhang, Yuyang, et al.
Veröffentlicht: (2026)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
von: Chen, Yifang, et al.
Veröffentlicht: (2024)

NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
von: Fan, Lizhou, et al.
Veröffentlicht: (2023)

Demystifying the unreasonable effectiveness of online alignment methods
von: Kang, Enoch Hyunwook
Veröffentlicht: (2026)

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

On Fine-Grained I/O Complexity of Attention Backward Passes
von: Li, Xiaoyu, et al.
Veröffentlicht: (2024)

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

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

Verifying Quantized Graph Neural Networks is PSPACE-complete
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

Unique Hard Attention: A Tale of Two Sides
von: Jerad, Selim, et al.
Veröffentlicht: (2025)

Context-Free Recognition with Transformers
von: Jerad, Selim, et al.
Veröffentlicht: (2026)

The Illusion of State in State-Space Models
von: Merrill, William, et al.
Veröffentlicht: (2024)

Why Are Linear RNNs More Parallelizable?
von: Merrill, William, et al.
Veröffentlicht: (2026)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
von: Fortnow, Lance
Veröffentlicht: (2025)

Topological entropy of Turing complete dynamics
von: Bruera, Renzo, et al.
Veröffentlicht: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
von: Alman, Josh, et al.
Veröffentlicht: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
von: Nalli, Sai Soumya, et al.
Veröffentlicht: (2026)

Stochastic Process Turing Machines
von: Wolpert, David, et al.
Veröffentlicht: (2024)

Exact Expressive Power of Transformers with Padding
von: Merrill, William, et al.
Veröffentlicht: (2025)

Learning Randomized Reductions
von: Erata, Ferhat, et al.
Veröffentlicht: (2024)

Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives
von: Meyerson, Elliot, et al.
Veröffentlicht: (2025)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
von: Svete, Anej, et al.
Veröffentlicht: (2026)