Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
share
In this paper, we seek a natural problem and a natural distribution of instances such that any O(n^c-ϵ)-time algorithm fails to solve most instances drawn from the distribution, while the problem admits an n^c+o(1)-time algorithm that correctly solves all instances. Specifically, we consider the K_a,b counting problem in a random bipartite graph, where K_a,b is a complete bipartite graph for constants a and b. We proved that the K_a,b counting problem admits an n^a+o(1)-time algorithm if a≥ 8, while any n^a-ϵ-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.
READ FULL TEXT