2020/10/12 by Hirahara, Shuichi, Shimizu, Nobutaka
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.05822
In this paper, we seek a natural problem and a natural distribution of instances such that any O(nc-ε)-time algorithm fails to solve most instances drawn from the distribution, while the problem admits an nc+o(1)-time algorithm that correctly solves all instances. Specifically, we consider the Ka,b counting problem in a random bipartite graph, where Ka,b is a complete bipartite graph for constants a and b. We proved that the Ka,b counting problem admits an na+o(1)-time algorithm if a≥ 8, while any na-ε-time algorithm fails to solve it even on random bipartite graph for any constant ε>0 under the Strong Exponential Time Hypotheis. Then, we amplify the hardness of this problem using the direct product theorem and Yao's XOR lemma by presenting a general framework of hardness amplification in the setting of fine-grained complexity.