New circuit size limits strengthen understanding of Boolean function complexity
Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness
Computational Complexity
Summary
This paper studies how certain Boolean functions, which involve true and false values, can be described or computed by special types of logical circuits. The authors found a way to break down complex formulas into simpler parts and proved that even the best possible small logical circuits cannot compute these functions efficiently when the circuits have limited depth. They also built some circuits that compute these functions but showed these circuits have to be quite large. These results help us understand the limitations of certain types of computation.
What this means in practice
- •For circuit designers: Exclude small, shallow AND/OR circuits as candidates for efficiently computing certain polynomial-time Boolean functions.
- •For cryptography engineers: Understand inherent limits on Boolean circuits computing functions related to cryptographic constructions to guide secure system design.
A theory result. No direct application yet.
Authors
Xin Li, Yan Zhong
Abstract
We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.