Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

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 and a and b are constants. Our distribution consists of the binomial random bipartite graphs Bαn,βn with edge density 1/2, where α and β are drawn uniformly at random from 1, …, a and 1, …, b, respectively. We determine the nearly optimal average-case complexity of this counting problem by proving the following results. Conditional Tight Worst-Case Complexity. Under the Strong Exponential Time Hypothesis, for any constants a ≥ 3 and ∊ > 0, there exists a constant b = b(a, ∊) such that no O(na–∊)-time algorithm counts the number of Ka,b subgraphs in a given n-vertex graph. On the other hand, for any constant a ≥ 8 and any b = b(n), we can count all Ka,b subgraphs in time bna+o(1). Worst-to-Average Reduction. If there exists a T(n)-time randomized heuristic algorithm that solves the Ka,b subgraph counting problem on a random graph Bαn,βn with success probability 1 — 1/polylog(n), then there exists a T(n)polylog(n)-time randomized algorithm that solves the Ka,b subgraph counting problem for any input with success probability 2/3. Fine-Grained Hardness Amplification. Suppose that there is a T(n)-time algorithm with success probability n–∊ that computes the parity of the number of Ka,b subgraphs in H, where is the disjoint union of k = O(∊ log n) i.i.d. random graphs G1, …, Gk each of which is drawn from the distribution of Bαn,βn. Then there is a T(n)nO(∊)-time randomized algorithm that counts Ka,b subgraphs for any input with success probability 2/3. The central idea behind these results is colorful subgraphs. For the first result, we reduce the k-Orthogonal Vectors problem to the colorful Ka,b detection problem. In the second result, we establish a worst-case-to-average-case reduction for a colorful subgraph counting problem based on the binary-extension technique given by [Boix-Adserà, Brennan, and Bresler; FOCS19]. Then, we reduce colorful Ka,b counting to Ka,b counting. Regarding the third result, we prove the classical XOR lemma and the direct product theorem in the fine-grained setting for subgraph counting problems. The core of the proof is an O(log n)-round doubly-efficient interactive proof system for the colorful subgraph counting problem such that the honest prover is asked to solve polylog(n) instances of the counting problem. The new protocol improves the known interactive proof system for the t-clique counting problem given by [Goldreich and Rothblum; FOCS18] in terms of query complexity.