Hardness Self-Amplification: Simplified, Optimized, and Unified

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 hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdős-Rényi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.

Our approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. We demonstrate that this reduction yields hardness selfamplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property. Our key technical contribution is to show the expansion property of the bipartite graph naturally constructed from the planted clique problem by using the coupling method of Markov chains.