All reports by Author Nobutaka Shimizu:

__
TR23-026
| 15th March 2023
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification: Simplified, Optimized, and Unified

__
TR22-108
| 18th July 2022
__

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

Shuichi Hirahara, Nobutaka Shimizu

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>

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