Summary
Computers run programs made of small steps called circuits, and understanding their limits is a big challenge. This paper studies a new kind of decision tree that asks about small pieces of the input, which can help prove limits on how efficiently these circuits work. The authors show that proving certain bounds for these local decision trees could lead to breakthroughs in understanding circuit complexity. They also find strong limits for simpler versions of these trees by exploring hidden patterns in special sets of sums called sumsets. Additionally, they look at decision trees based on quadratic queries, pointing toward future circuits that are harder to simplify.
What this means in practice
- •For circuit designers: Clarify theoretical limitations on log-depth circuits using local decision tree lower bounds.
- •For complexity theorists: Guide research on establishing stronger lower bounds for unrestricted-depth circuits leveraging quadratic decision trees.
A theory result. No direct application yet.
Abstract
We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.