# Realizable Circuit Complexity: Embedding Computation in Space-Time

arXiv: https://arxiv.org/abs/2509.19161 · HTML: https://mlsanity.com/paper/2509.19161/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 46 references that are in the map.
- First posted on arXiv 23 Sep 2025.

## Builds on (most cited first, 10 of 10)

- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Equilibrium Propagation: Bridging the Gap Between Energy-Based Models and Backpropagation](https://mlsanity.com/paper/1602.05179/) (2016)
- [Embodied Intelligence via Learning and Evolution](https://mlsanity.com/paper/2102.02202/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024)
- [Mortal Computation: A Foundation for Biomimetic Intelligence](https://mlsanity.com/paper/2311.09589/) (2023)

## Built on by (most cited first, 1 of 1)

- [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026)

## Abstract (arXiv)

Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes NC, AC, and TC treat unlimited fan-in, free interconnection, and polynomial gate counts as feasible -- assumptions that conflict with geometric, energetic, and thermodynamic realities. We introduce the family of realizable circuit classes RCd, which model computation embedded in physical d-dimensional space. Each circuit in RCd obeys conservative realizability laws: volume scales as O(td), cross-boundary information flux is bounded by O(td-1) per unit time, and growth occurs through local, physically constructible edits. These bounds apply to all causal systems, classical or quantum. Within this framework, we show that algorithms with runtime ω(nd/(d-1)) cannot scale to inputs of maximal entropy, and that any d-dimensional parallel implementation offers at most a polynomial speed-up of degree (d-1) over its optimal sequential counterpart. In the limit d→∞, RC_∞(polylog)=NC, recovering classical parallelism as a non-physical idealization. By unifying geometry, causality, and information flow, RCd extends circuit complexity into the physical domain, revealing universal scaling laws for computation.