Image de couverture de livre

Ask, and it shall be given: On the Turing completeness of prompting

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Qiu, Ruizhong, Xu, Zhe, Bao, Wenxuan, Tong, Hanghang
Format:	Preprint
Publié:	2024
Sujets:	Machine Learning Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

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

Constant Bit-size Transformers Are Turing Complete
par: Li, Qian, et autres
Publié: (2025)

Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization
par: Qiu, Ruizhong, et autres
Publié: (2024)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
par: Li, Qian, et autres
Publié: (2026)

Efficient Turing Machine Simulation with Transformers
par: Li, Qian, et autres
Publié: (2025)

Latte: Collaborative Test-Time Adaptation of Vision-Language Models in Federated Learning
par: Bao, Wenxuan, et autres
Publié: (2025)

Topological entropy of Turing complete dynamics
par: Bruera, Renzo, et autres
Publié: (2024)

Verifying Quantized Graph Neural Networks is PSPACE-complete
par: Sälzer, Marco, et autres
Publié: (2025)

Infinite Time Turing Machines and their Applications
par: Weerawarana, Rukmal, et autres
Publié: (2025)

Graph Data Selection for Domain Adaptation: A Model-Free Approach
par: Li, Ting-Wei, et autres
Publié: (2025)

On the Computational Hardness of Transformers
par: Saha, Barna, et autres
Publié: (2026)

A conservative Turing complete $S^4$ flow
par: Suárez-Serrato, Pablo
Publié: (2023)

Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
par: Qiu, Ruizhong, et autres
Publié: (2025)

Learnability of Parameter-Bounded Bayes Nets
par: Bhattacharyya, Arnab, et autres
Publié: (2024)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
par: Wang, Jie, et autres
Publié: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
par: Chandrasekaran, Gautam, et autres
Publié: (2024)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
par: Li, Zhiyuan, et autres
Publié: (2024)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
par: Seymour, Liam, et autres
Publié: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
par: Guo, Zizheng, et autres
Publié: (2024)

On the Hardness of Learning Regular Expressions
par: Attias, Idan, et autres
Publié: (2025)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
par: Merrill, William, et autres
Publié: (2025)

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

Spiky Rank and Its Applications to Rigidity and Circuits
par: Hambardzumyan, Lianna, et autres
Publié: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
par: Cherukuri, Kalyan, et autres
Publié: (2025)

Proximity to Losslessly Compressible Parameters
par: Farrugia-Roberts, Matthew
Publié: (2023)

Decision Tree Learning on Product Spaces
par: Moakahr, Arshia Soltani, et autres
Publié: (2026)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
par: Amiri, Alireza, et autres
Publié: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
par: Cao, Yang, et autres
Publié: (2025)

A Logic for Expressing Log-Precision Transformers
par: Merrill, William, et autres
Publié: (2022)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
par: Jacobs, Peter Matthew, et autres
Publié: (2026)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
par: Huang, Jizhou, et autres
Publié: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
par: Dwork, Cynthia, et autres
Publié: (2023)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
par: Rohatgi, Dhruv, et autres
Publié: (2025)

How Global Calibration Strengthens Multiaccuracy
par: Casacuberta, Sílvia, et autres
Publié: (2025)

Diffusion Language Models are Provably Optimal Parallel Samplers
par: Jiang, Haozhe, et autres
Publié: (2025)

Additive Models Explained: A Computational Complexity Approach
par: Bassan, Shahaf, et autres
Publié: (2025)

Certifiable Boolean Reasoning Is Universal
par: Li, Wenhao, et autres
Publié: (2026)

New Hardness Results for Low-Rank Matrix Completion
par: Chawin, Dror, et autres
Publié: (2025)

Reachability In Simple Neural Networks
par: Sälzer, Marco, et autres
Publié: (2022)

Hidden costs for inference with deep network on embedded system devices
par: Lee, Chankyu, et autres
Publié: (2026)