Smaller Depth-2 Linear Circuits for Disjointness Matrices
2026-03-16 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors improved the efficiency of certain two-layer circuits that compute a specific large matrix called the disjointness matrix. They found ways to build smaller circuits and circuits with lower degree than previously known. Their approach refines earlier methods by using a more controlled process related to random matrix theory and optimization. They also analyze different circuit types to find the best overall improvements for the degree bound.
depth-2 linear circuitsdisjointness matrixcircuit sizecircuit degreerebalancing frameworkLyapunov exponentrandom matrix productconvex optimizationcost landscapecircuit complexity
Authors
Lixi Ye
Abstract
We prove two new upper bounds for depth-2 linear circuits computing the $N$th disjointness matrix $D^{\otimes N}$. First, we obtain a circuit of size $O\big(2^{1.24485N}\big)$ over $\{0,1\}$. Second, we obtain a circuit of degree $O\big(2^{0.3199N}\big)$ over $\{0,\pm 1\}$. These improve the previous bounds of Alman and Li, namely size $O\big(2^{1.249424N}\big)$ and degree $O\big(2^{N/3}\big)$. Our starting point is the rebalancing framework developed in a line of works by Jukna and Sergeev, Alman, Sergeev, and Alman-Guan-Padaki, culminating in Alman and Li. We sharpen that framework in two ways. First, we replace the earlier "wild" rebalancing process by a tame, discretized process whose geometric-average behavior is governed by the quenched top Lyapunov exponent of a random matrix product. This allows us to invoke the convex-optimization upper bound of Gharavi and Anantharam. Second, for the degree bound we work explicitly with a cost landscape on the $(p,q)$-plane and show that different circuit families are dominant on different regions, so that the global maximum remains below $0.3199$.