Cover Image

The Agent Capability Problem: Predicting Solvability Through Information-Theoretic Bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Lutati, Shahar
Format:	Preprint
Published:	2025
Subjects:	Artificial Intelligence Computational Complexity Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Toward Optimal ANC: Establishing Mutual Information Lower Bound
by: Derrida, François, et al.
Published: (2025)

Algorithmic causal structure emerging through compression
by: Wendong, Liang, et al.
Published: (2025)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Exponential quantum advantage in processing massive classical data
by: Zhao, Haimeng, et al.
Published: (2026)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems
by: Azadi, Poria
Published: (2025)

Near-Optimal Learning and Planning in Separated Latent MDPs
by: Chen, Fan, et al.
Published: (2024)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
by: Li, Chenyang, et al.
Published: (2025)

Learning from Equivalence Queries, Revisited
by: Braverman, Mark, et al.
Published: (2026)

Circuit Complexity Bounds for Visual Autoregressive Model
by: Ke, Yekun, et al.
Published: (2025)

An Information Theoretic Perspective on Agentic System Design
by: He, Shizhe, et al.
Published: (2025)

A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
by: Zhang, Yuyang, et al.
Published: (2026)

Core Safety Values for Provably Corrigible Agents
by: Nayebi, Aran
Published: (2025)

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

A Communication-Theoretic Framework for LLM Agents: Cost-Aware Adaptive Reliability
by: Omidvar, Hamed, et al.
Published: (2026)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
by: Bhargav, Jayanth, et al.
Published: (2024)

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

Information-theoretic generalization bounds for learning from quantum data
by: Caro, Matthias, et al.
Published: (2023)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
by: Lou, Mengqi, et al.
Published: (2025)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

Machine Unlearning via Information Theoretic Regularization
by: Xu, Shizhou, et al.
Published: (2025)

An Effective Information Theoretic Framework for Channel Pruning
by: Chen, Yihao, et al.
Published: (2024)

An Information-Theoretic Criterion for Efficient Data Synthesis
by: Li, Hanyu, et al.
Published: (2026)

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

Analyzing and Improving Chain-of-Thought Monitorability Through Information Theory
by: Anwar, Usman, et al.
Published: (2026)

Theoretical limitations of multi-layer Transformer
by: Chen, Lijie, et al.
Published: (2024)

Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective
by: Laakom, Firas, et al.
Published: (2025)

Information-Theoretic State Variable Selection for Reinforcement Learning
by: Westphal, Charles, et al.
Published: (2024)

Uncertainty Quantification and Data Efficiency in AI: An Information-Theoretic Perspective
by: Simeone, Osvaldo, et al.
Published: (2025)

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

The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy
by: Emadi, Seyed Morteza
Published: (2026)

Context Channel Capacity: An Information-Theoretic Framework for Understanding Catastrophic Forgetting
by: Cheng, Ran
Published: (2026)

Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective
by: Yang, Jiaming, et al.
Published: (2026)

Laplace Sample Information: Data Informativeness Through a Bayesian Lens
by: Kaiser, Johannes, et al.
Published: (2025)

Information-Theoretic Policy Pre-Training with Empowerment
by: Schneider, Moritz, et al.
Published: (2025)

Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
by: Hazra, Rishi, et al.
Published: (2025)

A Theory of Learning with Autoregressive Chain of Thought
by: Joshi, Nirmit, et al.
Published: (2025)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
by: Chen, Bo, et al.
Published: (2025)

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