论文标题
在塞思下计数双智的几乎最佳的平均案例复杂性
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
论文作者
论文摘要
在本文中，我们寻求自然问题和实例的自然分布，以使任何$ o（n^{c-ε}）$ - 时间算法未能从分布中汲取大多数实例，而问题则承认$ n^{c+o（1）} $ - 时间算法可以正确解决所有实例。具体来说，我们考虑$ k_ {a，b} $计数问题，其中$ k_ {a，b} $是常数$ a $ a $和$ b $的完整的两部分图。我们证明了$ k_ {a，b} $计数问题承认，如果$ n^{a+o（1）} $ - 时间算法如果$ a \ geq 8 $，而任何$ n^{a-ε} $ - time time algorithm也无法在随机的bipartiite图形上以任何常数的$ pectient $ pecte $ε> terment fortient terement terement pertentient terement terement terement terement terement。然后，我们使用直接乘积定理和Yao的XOR引理来扩大此问题的硬度，并在精细颗粒复杂性的情况下提出硬度放大的一般框架。
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\geq 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.
