Fine-Grained ${\mathrm{AC}}^0$ Lower Bounds for $k$-$\mathrm{OV}$, $k$-$\mathrm{XOR}$, and $k$-$\mathrm{SUM}$ via Colored Subgraph Isomorphism

Abstract

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform ${\mathrm{AC}}^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega (k)}$ for $k$-OV and $(n/k{)}^{\Omega (k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth. For growing $k=n^{o(1)}$ and every fixed depth $d$, we obtain the unconditional floor $n^{{\Omega }_d(\min \{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega (k)}$ at depth two for both top-gate orientations, and at depth three for top-disjunction (OR-AND-OR) circuits, with no restriction on fan-in or polarity. The depth-three argument rests on a minterm bound for a single CNF: a fixed CNF is very unlikely to become true for the first time exactly when a randomly planted copy is completed. Assuming a pattern-uniform strengthening of the Li-Razborov-Rossman source lower bound, the same projections complete the $k=n^{o(1)}$ frontier with $n^{{\Omega }_d(k)}$ for the missing top-conjunction depth-three orientation and for every fixed depth $d\ge 4$. The framework is modular in the source bound, so improved source bounds pass directly to all three targets. All direct $k$-XOR bounds concern odd $k$; a black-box lift covers even $k$, and the $k$-SUM projection works for both parities. At the bit width $m=\Theta (k\log (\mathrm{e}n/k))$ used by our projection, a block-carry ${\Sigma }_3$ upper bound of size $(n/k{)}^{O(k)}$ matches the depth-three lower bound up to constants in the exponent. Gaps remain at depth two and for top-conjunction depth three.

This version adds an unconditional depth-three lower bound for top-disjunction (OR-AND-OR) circuits with an exponent linear in growing k; adds worked toy instances that display the projection to each of the three targets; and revises the presentation throughout, correcting typos, simplifying overloaded notations and terminologies, and adding pointers to the formal definitions and statements