ECCC-Report TR22-108https://eccc.weizmann.ac.il/report/2022/108Comments and Revisions published for TR22-108en-usSun, 24 Jul 2022 06:28:50 +0300
Paper TR22-108
| Hardness Self-Amplification from Feasible Hard-Core Sets |
Shuichi Hirahara,
Nobutaka Shimizu
https://eccc.weizmann.ac.il/report/2022/108We 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$.Sun, 24 Jul 2022 06:28:50 +0300https://eccc.weizmann.ac.il/report/2022/108