We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can be converted into PRGs of sub-polynomial seed length.

- Hardness under natural distributions: If $\mathrm{E}$ (deterministic exponential time) is average-case hard against $\mathcal{C}$ under some distribution, then $\mathrm{E}$ is average-case hard against $\mathcal{C}$ under the uniform distribution.

- Equivalence between worst-case and average-case hardness: Worst-case lower bounds against $\mathrm{MAJ} \circ \mathcal{C}$ for problems in $E$ are equivalent to strong average-case lower bounds against $\mathcal{C}$. This can be seen as a certain converse to the Discriminator Lemma [Hajnal et al., JCSS'93].

These results were not known to hold for circuit classes that do not compute majority. Additionally, we prove that classical and recent approaches to worst-case lower bounds against $\mathrm{ACC}^0$ via communication lower bounds for NOF multi-party protocols [Hastad and Goldmann, CC'91; Razborov and Wigderson, IPL'93] and Torus polynomials degree lower bounds [Bhrushundi et al., ITCS'19] also imply strong average-case hardness against $\mathrm{ACC}^0$ under the uniform distribution.

Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority ($\mathrm{MAJ}$) and Approximate Linear Sum ($\widetilde{\mathrm{SUM}}$) gates. Roughly speaking, while a $\mathrm{MAJ}$ gate outputs $1$ when the sum of the $m$ input bits is at least $m/2$, a $\widetilde{\mathrm{SUM}}$ gate computes a real-valued bounded weighted sum of the input bits and outputs $1$ (resp. $0$) if the sum is close to $1$ (resp. close to $0$), with the promise that one of the two cases always holds. As part of our framework, we explore ideas introduced in [Chen and Ren, STOC'20] to show that, for the purpose of proving lower bounds, a top layer $MAJ$ gate is equivalent to a (weaker) $\widetilde{\mathrm{SUM}}$ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of $\mathrm{MAJ}$ and $\widetilde{\mathrm{SUM}}$ gates. Among them, we prove that:

- Lower bound: $\mathrm{NQP}$ does not admit fixed quasi-polynomial size $\mathrm{MAJ} \circ \widetilde{\mathrm{SUM}} \circ \mathrm{ACC}^0 \circ \mathrm{THR}$ circuits.

This is the first explicit lower bound against circuits with distinct layers of $\mathrm{MAJ}$, $\widetilde{\mathrm{SUM}}$, and $\mathrm{THR}$ gates. Consequently, if the aforementioned equivalence between $\mathrm{MAJ}$ and $\widetilde{\mathrm{SUM}}$ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class $\mathrm{THR} \circ \mathrm{THR}$ of depth-$2$ polynomial-size threshold circuits would follow.