We prove lower bounds for $k$-$\mathrm{OV}$, $k$-$\mathrm{XOR}$, and $k$-$\mathrm{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 every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-$\mathrm{OV}$ and $(n/k)^{\Omega(k)}$ for $k$-$\mathrm{XOR}$ and $k$-$\mathrm{SUM}$, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, 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, i.e., top conjunction and top disjunction, and at depth three for top-disjunction circuits $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{OR}$, with no restriction on bottom fan-in or literal 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, with no circuit-correctness hypothesis. 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 \geq 4$. The interface of our projection framework does not depend on which source lower bound is used, so new lower bounds for suitable source families or improved source exponents pass directly to all three targets. All direct $k$-$\mathrm{XOR}$ bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-$\mathrm{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 top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

(Fixed ECCC webpage display issues)

This version adds an unconditional depth-three lower bound result 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.

We prove lower bounds for $k$-$\mathsf{OV}$, $k$-$\mathsf{XOR}$, and $k$-$\mathsf{SUM}$ in nonuniform $\mathsf{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 every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-$\mathsf{OV}$ and $(n/k)^{\Omega(k)}$ for $k$-$\mathsf{XOR}$ and $k$-$\mathsf{SUM}$, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, 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, i.e., top conjunction and top disjunction, and at depth three for top-disjunction circuits $\mathsf{OR} \circ \mathsf{AND} \circ \mathsf{OR}$, with no restriction on bottom fan-in or literal 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, with no circuit-correctness hypothesis. 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 \geq 4$. The interface of our projection framework does not depend on which source lower bound is used, so new lower bounds for suitable source families or improved source exponents pass directly to all three targets. All direct $k$-$\mathsf{XOR}$ bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-$\mathsf{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 top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

This version adds an unconditional depth-three lower bound result 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.

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform 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 every 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, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, 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, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{\Omega_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = \Theta(k\log(en/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.