{"total":53,"rows":[{"id":"2305.18654","title":"Faith and Fate: Limits of Transformers on Compositionality","created":"2023-05-29","cited_by_count":503,"area":null},{"id":"2404.08819","title":"The Illusion of State in State-Space Models","created":"2024-04-12","cited_by_count":187,"area":null},{"id":"2311.00208","title":"What Formal Languages Can Transformers Express? A Survey","created":"2023-11-01","cited_by_count":124,"area":null},{"id":"2402.09268","title":"Transformers, parallel computation, and logarithmic depth","created":"2024-02-14","cited_by_count":79,"area":null},{"id":"2402.09963","title":"Why are Sensitive Functions Hard for Transformers?","created":"2024-02-15","cited_by_count":74,"area":null},{"id":"2503.03961","title":"A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers","created":"2025-03-05","cited_by_count":53,"area":null},{"id":"2405.17394","title":"The Expressive Capacity of State Space Models: A Formal Language Perspective","created":"2024-05-27","cited_by_count":46,"area":null},{"id":"2404.04393","title":"Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers","created":"2024-04-05","cited_by_count":39,"area":null},{"id":"2502.19249","title":"Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases","created":"2025-02-26","cited_by_count":37,"area":null},{"id":"2505.16381","title":"PaTH Attention: Position Encoding via Accumulating Householder Transformations","created":"2025-05-22","cited_by_count":34,"area":null},{"id":"2404.14994","title":"Transformers Can Represent $n$-gram Language Models","created":"2024-04-23","cited_by_count":32,"area":null},{"id":"2406.09347","title":"Separations in the Representational Capabilities of Transformers and Recurrent Architectures","created":"2024-06-13","cited_by_count":29,"area":null},{"id":"2411.07602","title":"Circuit Complexity Bounds for RoPE-based Transformer Architecture","created":"2024-11-12","cited_by_count":26,"area":null},{"id":"2505.23623","title":"Characterizing the Expressivity of Fixed-Precision Transformer Language Models","created":"2025-05-29","cited_by_count":14,"area":null},{"id":"2412.18040","title":"Theoretical Constraints on the Expressive Power of $\\mathsf{RoPE}$-based Tensor Attention Transformers","created":"2024-12-23","cited_by_count":12,"area":null},{"id":"2506.16055","title":"Knee-Deep in C-RASP: A Transformer Depth Hierarchy","created":"2025-06-19","cited_by_count":12,"area":null},{"id":"2503.01805","title":"Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers","created":"2025-03-03","cited_by_count":11,"area":null},{"id":"2411.01992","title":"Ask, and it shall be given: On the Turing completeness of prompting","created":"2024-11-04","cited_by_count":10,"area":null},{"id":"2501.04299","title":"Circuit Complexity Bounds for Visual Autoregressive Model","created":"2025-01-08","cited_by_count":10,"area":null},{"id":"2502.16490","title":"On Computational Limits of FlowAR Models: Expressivity and Efficiency","created":"2025-02-23","cited_by_count":10,"area":null},{"id":"2503.14615","title":"Unique Hard Attention: A Tale of Two Sides","created":"2025-03-18","cited_by_count":10,"area":null},{"id":"2412.05562","title":"Modern Hopfield Networks Require Chain-of-Thought to Solve $\\mathsf{NC}^1$-Hard Problems","created":"2024-12-07","cited_by_count":9,"area":null},{"id":"2505.11199","title":"The Counting Power of Transformers","created":"2025-05-16","cited_by_count":9,"area":null},{"id":"2404.02040","title":"Transformers as Transducers","created":"2024-04-02","cited_by_count":8,"area":null},{"id":"2510.27015","title":"Quantitative Bounds for Length Generalization in Transformers","created":"2025-10-30","cited_by_count":8,"area":null},{"id":"2304.07687","title":"MLRegTest: A Benchmark for the Machine Learning of Regular Languages","created":"2023-04-16","cited_by_count":7,"area":null},{"id":"2405.18548","title":"Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning","created":"2024-05-28","cited_by_count":5,"area":null},{"id":"2410.01600","title":"ENTP: Encoder-only Next Token Prediction","created":"2024-10-02","cited_by_count":5,"area":null},{"id":"2510.05364","title":"The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures","created":"2025-10-06","cited_by_count":4,"area":null},{"id":"2601.01754","title":"Context-Free Recognition with Transformers","created":"2026-01-05","cited_by_count":4,"area":null},{"id":"2603.02238","title":"Length Generalization Bounds for Transformers","created":"2026-02-13","cited_by_count":4,"area":null},{"id":"2503.10542","title":"Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More","created":"2025-03-13","cited_by_count":3,"area":null},{"id":"2602.11175","title":"Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth","created":"2026-01-19","cited_by_count":3,"area":null},{"id":"2309.00857","title":"Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languages","created":"2023-09-02","cited_by_count":2,"area":null},{"id":"2405.04515","title":"A Transformer with Stack Attention","created":"2024-05-07","cited_by_count":2,"area":null},{"id":"2602.21307","title":"SymTorch: Symbolic Distillation of Neural Networks","created":"2026-02-24","cited_by_count":2,"area":null},{"id":"2312.09048","title":"On The Expressivity of Recurrent Neural Cascades","created":"2023-12-14","cited_by_count":1,"area":null},{"id":"2406.12915","title":"How Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliability","created":"2024-06-13","cited_by_count":1,"area":null},{"id":"2407.10949","title":"Representing Rule-based Chatbots with Transformers","created":"2024-07-15","cited_by_count":1,"area":null},{"id":"2505.10719","title":"Tracr-Injection: Distilling Algorithms into Pre-trained Language Models","created":"2025-05-15","cited_by_count":1,"area":null},{"id":"2505.22081","title":"Can Test-time Computation Mitigate Reproduction Bias in Neural Symbolic Regression?","created":"2025-05-28","cited_by_count":1,"area":null},{"id":"2506.18739","title":"On the Existence of Universal Simulators of Attention","created":"2025-06-23","cited_by_count":1,"area":null},{"id":"2509.19161","title":"Realizable Circuit Complexity: Embedding Computation in Space-Time","created":"2025-09-23","cited_by_count":1,"area":null},{"id":"2602.02707","title":"Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers","created":"2026-02-02","cited_by_count":1,"area":null},{"id":"2602.07599","title":"Rational Transductors","created":"2026-02-07","cited_by_count":1,"area":null},{"id":"2405.11657","title":"On the Expressivity of Recurrent Neural Cascades with Identity","created":"2024-05-19","cited_by_count":0,"area":null},{"id":"2510.05494","title":"Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective","created":"2025-10-07","cited_by_count":0,"area":null},{"id":"2511.02825","title":"Neurosymbolic Deep Learning Semantics","created":"2025-11-04","cited_by_count":0,"area":null},{"id":"2605.07705","title":"Encoder-Decoder Transformers: Logical Characterizations and Periodicity","created":"2026-05-08","cited_by_count":0,"area":null},{"id":"2605.22964","title":"Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization","created":"2026-05-21","cited_by_count":0,"area":null},{"id":"2608.12671","title":"On the Expressive Power of Transformers","created":"2026-08-13","cited_by_count":0,"area":null},{"id":"2609.08851","title":"Length Generalization for Transformers via Compression","created":"2026-09-08","cited_by_count":0,"area":null},{"id":"2609.31999","title":"VC Dimension and Expressivity of Real-Valued Transformers","created":"2026-09-25","cited_by_count":0,"area":null}],"next_cursor":null}