Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
复制标题
DOI：
10.1137/1.9781611976465.140
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Shuichi Hirahara;Nobutaka Shimizu
中科院分区：
文献类型：
--
作者：
Shuichi Hirahara;Nobutaka Shimizu
在本文中，我们寻求一个自然问题和一个自然分布的实例，使得任何$O(n^{c-\epsilon})$-time算法都不能解决从分布中提取的大多数实例，而该问题允许一个$n^{c+o(1)}$-time算法正确地解决所有实例。具体地说，我们考虑了随机二部图中的$K_{a，b}$计数问题，其中$K_{a，b}$是关于常数$a$和$b$的完全二部图。我们证明了当$a8$时，$Ka，b}计数问题存在一个$n^{a+o(1)}$-time算法，而任何$n^{a-epsilon}$-time算法在强指数时间假设下，即使是在任意二部图上也不能解它.然后，我们利用直积定理和姚的异或引理，通过给出细粒度复杂性背景下的硬度放大的一般框架，放大了该问题的难度。
In this paper, we seek a natural problem and a natural distribution of instances such that any $O(n^{c-\epsilon})$-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\geq 8$, while any $n^{a-\epsilon}$-time algorithm fails to solve it even on random bipartite graph for any constant $\epsilon>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.