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

Haoxing Lin

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. O…