Comprehensive Research Summary — July 2026
Theoretical Computer Science (TCS) provides the formal backbone for understanding what neural networks can and cannot compute, the fundamental limits of learning, and the provable boundaries of quantum and classical machine learning.
The question of whether depth fundamentally increases expressive power has been decisively answered in the affirmative by a line of work beginning with Telgarsky (2016) and Eldan & Shamir (2016).
Telgarsky (2016) — "Benefits of Depth in Neural Networks" (arXiv:1602.04485). Proved that deep ReLU networks can represent functions with exponentially more linear regions than shallow ones of comparable size. Specifically, a deep network with O(k) layers can produce a function with Omega(2^k) linear regions, while any shallow network requires exponentially many neurons to match. This formalizes the intuition that depth enables compositional feature reuse.
Eldan & Shamir (2016) — "The Power of Depth for Feedforward Neural Networks" (arXiv:1512.03965). Constructed a simple radial function on R^d expressible by a 3-layer network that cannot be epsilon-approximated by any 2-layer network unless its width is exponential in d. The result holds for ReLU, sigmoid, and threshold activations, proving depth separation is not an artifact of a particular activation function.
Subsequent work: Chatziafratis et al. (2019) — "Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem" (arXiv:1912.04378) extended these results using dynamical systems theory, showing that depth-width trade-offs are inherent to ReLU networks and cannot be circumvented.
Open problem: Exact characterization of the depth-width trade-off for arbitrary architectures remains incomplete. The gap between upper bounds (existence of efficient deep representations) and lower bounds (provable shallow limitations) is still large for modern architectures like transformers and graph neural networks.
Transformers, the dominant architecture in NLP and beyond, have been systematically studied through the lens of circuit complexity.
Merrill, Sabharwal & Smith (2021) — "Saturated Transformers Are Constant-Depth Threshold Circuits" (arXiv:2106.16213). Showed that transformers with saturated attention (a formal idealization of hard attention) fall within TC0 -- the class of problems computable by constant-depth, polynomial-size circuits with threshold gates (majority gates). This places transformers in a relatively low complexity class, on par with neural networks with threshold activation.
Merrill & Sabharwal (2022) — "The Parallelism Tradeoff: Limitations of Log-Precision Transformers" (arXiv:2207.00729). Extended the analysis to log-precision transformers (fixed-precision arithmetic with precision logarithmic in input length). Proved that such transformers can be simulated by TC0 circuits, meaning they cannot solve problems outside TC0 -- notably, they cannot compute parity, graph connectivity, or multiplication. This establishes a formal parallelism tradeoff: the more parallel the transformer (i.e., limited depth), the more restricted its expressivity, unless depth grows with input length.
Merrill & Sabharwal (2023) — Further refined the expressivity hierarchy, showing that transformers with CoT (chain-of-thought) can break out of TC0 into P-complete problems, effectively simulating sequential computation via intermediate token generation. This provides a theoretical explanation for why prompting strategies (CoT, scratchpads) dramatically extend transformer capabilities.
Liu et al. (2023) — Analyzed the uniform-TC0 expressivity of masked transformers, proving that masked self-attention with causal masking corresponds exactly to the complexity class L (logspace) under certain precision constraints, while bidirectional attention reaches TC0.
Feng et al. (2023) — Extended the analysis to the LOGSPACE/PTIME hierarchy, proving that transformers with position encodings fall into NC1 when depth is bounded, and that transformer encoders with hard attention characterize exactly AC0 (constant-depth, unbounded fan-in circuits with AND/OR gates).
Current status (2024-2026): The field has converged on a nuanced picture:
- Bounded-depth transformers (standard pre-trained models) lie in TC0 subset of NC1
- Transformers with CoT can reach P (can simulate Turing machines)
- Precision is the key resource: log-precision gives TC0, full precision with unbounded depth gives P-completeness.
- Recurrent memory (RWKV, Mamba-style architectures) traverses a different trade-off: constant memory per step vs. quadratic attention.
Frontier question: Do there exist problems in TC0 that cannot be efficiently approximated by log-precision transformers of feasible size? This touches on the intersection of circuit complexity, learnability, and approximation theory.