Optimal Lower Bounds for Symmetric Modular Circuits
This solves a foundational problem in circuit complexity theory, providing tight bounds for symmetric modular circuits, though it is incremental as it focuses on a restricted model.
The paper tackles the long-standing open problem of proving lower bounds for modular circuits computing the Boolean AND function, achieving subexponential lower bounds for symmetric circuits under all permutations of inputs, which precisely matches a known construction, showing optimal size is achieved at depth 2.
A notorious open question in circuit complexity is whether Boolean operations of arbitrary arity can efficiently be expressed using modular counting gates only. HÃ¥stad's celebrated switching lemma yields exponential lower bounds for the dual problem - realising modular arithmetic with Boolean gates - but, a similar lower bound for modular circuits computing the Boolean AND function has remained elusive for almost 30 years. We solve this problem for the restricted model of symmetric circuits: We consider MOD$_m$-circuits of arbitrary depth, and for an arbitrary modulus $m \in \mathbb{N}$, and obtain subexponential lower bounds for computing the $n$-ary Boolean AND function, under the assumption that the circuits are syntactically symmetric under all permutations of their $n$ input gates. This lower bound is matched precisely by a construction due to (Idziak, KawaÅek, Krzaczkowski, LICS'22), leading to the surprising conclusion that the optimal symmetric circuit size is already achieved with depth $2$. Motivated by another construction from (LICS'22), which achieves smaller size at the cost of greater depth, we also prove tight size lower bounds for circuits with a more liberal notion of symmetry characterised by a nested block structure on the input variables.