Key papers

• Token Rankings are Unforgeable Language Model Signatures (2026)
  Matthew Finlayson et al.
  1.89
• Enhanced and Efficient Reasoning in Large Learning Models (2026)
  Leslie G. Valiant
  1.83
• A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits (2026)
  Yuyang Zhang et al.
  1.83
• The Root Theorem of Context Engineering (2026)
  Borja Odriozola Schick
  1.78
• Why Are Linear RNNs More Parallelizable? (2026)
  William Merrill and Hongjian Jiang and Yanhong Li and Anthony Lin and Ashish Sabharwal
  1.72
• A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention (2026)
  Xiaowei Ye et al.
  1.67
• Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy (2025)
  Robert Ganian et al.
  1.50
• On the Hardness of Learning Regular Expressions (2025)
  Idan Attias and Lev Reyzin and Nathan Srebro and Gal Vardi
  1.44
• Perfect diffusion is TC⁰ -- Bad diffusion is Turing-complete (2025)
  Yuxi Liu
  1.28
• Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition (2025)
  Rishi Hazra et al.
  1.11
• Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent (2025)
  Bo Chen et al.
  1.11
• A Theory of Learning with Autoregressive Chain of Thought (2025)
  Nirmit Joshi et al.
  1.06
• Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding (2025)
  Yifang Chen et al.
  1.06
• BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity? (2025)
  Pierre Chambon et al.
  1.06
• On the Computational Tractability of the (Many) Shapley Values (2025)
  Reda Marzouk et al.
  1.00
• Hadamard Row-Wise Generation Algorithm (2024)
  Brayan Monroy and Jorge Bacca
  —
• Journalists, Emotions, and the Introduction of Generative AI Chatbots: A Large-Scale Analysis of Tweets Before and After the Launch of ChatGPT (2024)
  Seth C. Lewis et al.
  —
• On Fine-Grained I/O Complexity of Attention Backward Passes (2024)
  Xiaoyu Li et al.
  —
• Unlocking the Theory Behind Scaling 1-Bit Neural Networks (2024)
  Majid Daliri et al.
  —
• Kleene algebra with commutativity conditions is undecidable (2024)
  Arthur Azevedo de Amorim et al.
  —
• Theoretical limitations of multi-layer Transformer (2024)
  Lijie Chen et al.
  —
• The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity (2024)
  Yifang Chen et al.
  —
• Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving (2024)
  Marwan AbdElhameed et al.
  —
• Knowledge as a Breaking of Ergodicity (2024)
  Yang He and Vassiliy Lubchenko
  —
• RoPE Attention Can Be Trained in Almost Linear Time (2024)
  Yang Cao et al.
  —