The Nth disjointness matrix encodes whether two sets are disjoint — an N-by-N matrix over subsets where each entry is 1 if the row and column subsets share no elements and 0 otherwise. Computing this matrix with depth-2 linear circuits — two layers of linear combinations — requires exponentially many operations, but the exponent matters. Ye improves the upper bound to O(2^{1.245N}), beating prior work by Alman and Li.
The method treats circuit construction as a dynamical system. The key move replaces an earlier “wild” rebalancing process — which adjusted circuit parameters heuristically — with a “tame, discretized process whose geometric-average behavior is governed by the quenched top Lyapunov exponent.” The Lyapunov exponent, borrowed from dynamical systems theory, measures the average rate at which nearby trajectories converge or diverge. Here it governs how efficiently the circuit distributes computation across its two layers.
The second insight maps the degree bound onto a cost landscape in the (p,q)-plane, where different circuit families dominate in different regions. The optimal circuit is not a single construction but a patchwork — different architectural choices win in different parameter regimes, and the overall bound comes from stitching together the best local choices.
Circuit optimization is not usually framed as dynamics. The connection works because the rebalancing process that improves circuits is iterative, and iterative processes have trajectories, and trajectories have stability properties. Importing Lyapunov stability theory — a tool for continuous dynamical systems — into discrete circuit construction is the kind of cross-domain transfer that works precisely when the structural relationship is real rather than metaphorical. The system being optimized has dynamics; the dynamics have a characteristic exponent; the exponent bounds the optimization.