:: Library Catalog

Image de couverture de livre

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Casacuberta, Sílvia, Gopalan, Parikshit, Kanade, Varun, Reingold, Omer
Format:	Preprint
Publié:	2025
Sujets:	Machine Learning Computational Complexity
Accès en ligne:	https://arxiv.org/abs/2504.15206
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On Computationally Efficient Multi-Class Calibration
par: Gopalan, Parikshit, et autres
Publié: (2024)

Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration
par: Gopalan, Parikshit, et autres
Publié: (2023)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
par: Gopalan, Parikshit, et autres
Publié: (2024)

Calibration through the Lens of Indistinguishability
par: Gopalan, Parikshit, et autres
Publié: (2025)

Complexity-Theoretic Implications of Multicalibration
par: Casacuberta, Sílvia, et autres
Publié: (2023)

The communication complexity of distributed estimation
par: Gopalan, Parikshit, et autres
Publié: (2025)

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

Representative Language Generation
par: Peale, Charlotte, et autres
Publié: (2025)

Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
par: London, Charles, et autres
Publié: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
par: Bassan, Shahaf, et autres
Publié: (2024)

Provable Uncertainty Decomposition via Higher-Order Calibration
par: Ahdritz, Gustaf, et autres
Publié: (2024)

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

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)

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

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)

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

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
par: Rohatgi, Dhruv, 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)

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

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

Smoothed Agnostic Learning of Halfspaces over the Hypercube
par: Kou, Yiwen, et autres
Publié: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
par: Jacot, Arthur
Publié: (2025)

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

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

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

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)

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

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

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

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

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

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

Ask, and it shall be given: On the Turing completeness of prompting
par: Qiu, Ruizhong, et autres
Publié: (2024)

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

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

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