We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness self-amplification results for natural distributional problems studied in fine-grained average-case complexity, such as the problem of counting the number of the triangles modulo 2 in a random tripartite graph and the online vector-matrix-vector multiplication problem over $\mathbb{F}_2$. More generally, we show that any problem that can be decomposed into ``computationally disjoint'' subsets of inputs admits hardness self-amplification. This is proved by generalizing the security proof of the Nisan--Wigderson pseudorandom generator, in which case nearly disjoint subsets of inputs are considered.

At the core of our proof techniques is a new notion of feasible hard-core set, which generalizes Impagliazzo's hard-core set [Impagliazzo, FOCS'95]. We show that any weak average-case hard function $f$ has a feasible hard-core set $H$: any small $H$-oracle circuit (that is allowed to make queries $q$ to $H$ if $f(q)$ can be computed without the oracle) fails to compute $f$ on a $(\frac{1}{2} - o(1))$-fraction of inputs in $H$.