All reports by Author Nobutaka Shimizu:

__
TR22-108
| 18th July 2022
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification from Feasible Hard-Core Sets

Shuichi Hirahara, Nobutaka Shimizu

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 ... more >>>