In the previous post, we did two examples of proving average-case fine-grained hardness via worst-case to average-case reductions. In this post, I want to continue the discussion of counting $t$-cliques (in particular, on Erdős–Rényi graphs) to showcase a new technique, which builds on the general recipe and the example of counting $t$-cliques described in the previous post. In the next post, I will discuss how this new technique can be applied to some other combinatorial problems.

Counting $t$-cliques in Erdős–Rényi graph. A strong follow-up [BBB19] of the result [GR18] we discussed in the previous post shows that there is an $\widetilde{O}(n^2)$-time reduction from counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques with error probability $<\frac{1}{\log^{O(1)} n}$ in Erdős–Rényi graph (whereas the sampable distribution of the random graph in [GR18] is somewhat unnatural). The key idea is a decomposition lemma which says for sufficiently large prime $p$ and $k=O(\log(p)\log(p/\varepsilon))$, for any constants $0 (for our application, these constants will be equal), given independent Bernoulli random variables $y_{\ell}\sim\textrm{Bern}(p^{(\ell)})$, the distribution of $\sum_{\ell=0}^k 2^{\ell}y_{\ell}\mod p$ is close to the uniform distribution over $\mathbf{F}_{p}$, i.e., the statistical distance is less than $\varepsilon$ (later when we apply this lemma, we want $\varepsilon$ to be $1/\textrm{poly}(n)$, and therefore $k=O(\log p\cdot(\log p+\log n))$ ). We skip the proof of this lemma which is a nice application of basic Fourier analysis.

As in the previous post, $f_{t\textrm{-clique}}$ denotes a constructed polynomial that computes the number of $t$-cliques when the input is an adjacency matrix of a graph. The step 3 of the general recipe from the previous post reduces counting $t$-cliques for the worst-case graph to evaluating $f_{t\textrm{-clique}}(Y)$ on $d+1$ many uniformly random $Y\in\mathbf{F}_{p}^{n^2}$ (recall in the previous post, $d$ is the degree of the polynomial $f_{t\textrm{-clique}}$, and $p$ is $O(t\log n)$ after the Chinese remaindering trick). Based on the decomposition lemma, using standard sampling scheme (this is essentially rejection sampling, which I will not go into the details, but I just want to mention that we would like the $\varepsilon$ in the decomposition lemma to be $1/\textrm{poly}(n)$ such that the sampling scheme succeeds w.h.p. by a few attempts), we can further reduce evaluating $f_{t\textrm{-clique}}(Y)$ on uniformly random $Y\in\mathbf{F}_{p}^{n^2}$ to evaluating $f_{t\textrm{-clique}}(\sum_{\ell=0}^k 2^{\ell} Y_{\ell})$, where each $Y_{\ell}$ is a random 0-1 valued matrix that is statistically close to the adjacency matrix of an Erdős–Rényi graph. Now, if we can “pull out” the weighted sum in $f_{t\textrm{-clique}}(\sum_{\ell=0}^k 2^{\ell} Y_{\ell})$, then we are done, because evaluating $f_{t\textrm{-clique}}$ on the adjacency matrix of an Erdős–Rényi graph is precisely counting $t$-cliques for Erdős–Rényi graph.

When can we “pull out” the weighted sum for a polynomial $f(\sum_{\ell=0}^k 2^{\ell} Y_{\ell})$? One answer is when the polynomial is $d$-partite.

An $m$-variate polynomial $f(x_1,\dots,x_m)$ is $d$-partite if there is a partition of the set of variables $\dot{\bigcup}_{j\in[d]} S_j=[m]$ such that $f$ is the sum of monomials in which each monomial contains exactly one variable from each part $S_j$ (more formally, $f(x_1,\dots,x_m)=\sum_{(i_1,i_2,\dots,i_d)\in S}\prod_{j\in[d]}x_{i_j}$ for some $S\subseteq S_1\times S_2\times\dots\times S_d$).

For $d$-partite polynomial $f$, it is not hard to show that
$f(\sum_{\ell=0}^k 2^{\ell}y_{1,\ell},\dots,\sum_{\ell=0}^k 2^{\ell}y_{m,\ell})=\sum_{\ell_1=0}^k\sum_{\ell_2=0}^k\dots\sum_{\ell_d=0}^k 2^{\ell_1+\dots+\ell_d}\cdot f(y_{1,\ell_1},\dots,y_{m,\ell_m}).$
(Essentially, because two variables from the same $S_i$ never appear in the same monomial, we can enumerate variables from the same $S_i$ in the same order.)

Let us think of each $y_{i,\ell}$ as a coordinate of Erdős–Rényi adjacency matrix $Y_{\ell}$, then $f(y_{1,\ell_1},\dots,y_{m,\ell_m})$ is evaluating $f$ on an ensemble of distinct coordinates of $Y_{\ell}$‘s, and such ensemble is obviously Erdős–Rényi as well. Therefore, we have managed to decompose $f(\sum_{\ell=0}^k 2^{\ell} Y_{\ell})$ into sum of $k^d$ many $f(Y^{(\ell_1,\dots,\ell_d)})$‘s where each $Y^{(\ell_1,\dots,\ell_d)}$ denotes an Erdős–Rényi adjacency matrix. In the next paragraph, we will construct a $d=\binom{t}{2}$-partite polynomial $f_{t\textrm{-clique}}$ for counting $t$-cliques, and therefore, we have reduced computing $f_{t\textrm{-clique}}(\sum_{\ell=0}^k 2^{\ell} Y_{\ell})$ to computing $k^{\binom{t}{2}}=\log^{O(1)} n$ many $f_{t\textrm{-clique}} (Y^{(\ell_1,\dots,\ell_d)})$‘s, which is a mild blow-up of the number of the random instances which the reduction needs to solve. (In general, we consider the reduction to be efficient when the number of random instances it needs to solve is $n^{o(1)}$, and hence, as long as $d=o(\log n/\log \log n)$, we are good to go.)

Unfortunately, the $f_{t\textrm{-clique}}$ given in the previous post does not work. Instead, we first reduce counting $t$-cliques in any graph to counting $t$-cliques in a $t$-partite graph, and then we construct a $\binom{t}{2}$-partite polynomial $f_{t\textrm{-clique}}$ for counting $t$-cliques in a $t$-partite graph. Reduction from counting $t$-cliques in any graph to counting $t$-cliques in a $t$-partite graph is standard. Simply consider the tensor product between the original graph and another $t$-clique. The number of $t$-cliques in the tensor product graph is exactly $t!$ times that in the original graph. Now given the $t$-paritite graph, let $V_i$ denote the $i$-th part of vertices, and let $X^{(i,j)}$ (for $i) denote the adjacency matrix between $V_i$ and $V_j$. Consider the new polynomial $f_{t\textrm{-clique}}(X^{(1,2)},X^{(1,3)},\dots,X^{(t-1,t)}):=\sum_{v_1\in V_1}\sum_{v_2\in V_2}\dots\sum_{v_t\in V_t}\prod_{(i,j)\in\binom{[t]}{2}} X_{v_i,v_j}^{(i,j)}$, where $X_{v_i,v_j}^{(i,j)}$ denotes the coordinate that indicates if there is an edge between $v_i,v_j$. Observe that $f_{t\textrm{-clique}}$ counts $t$-cliques by picking one vertex for each part and checking if these $t$ vertices form a clique. It is indeed $\binom{t}{2}$-partite as each $X^{(i,j)}$ corresponds to a part of variables.

New recipe for worst-case to average-case reductions. Let us take a minute to think about what structural properties of counting $t$-cliques we have used in the entire reduction except for constructing $f_{t\textrm{-clique}}$.

The answer is none! The only part specific to counting $t$-cliques was cooking up a $d$-partite polynomial for $d=o(\log n/\log \log n)$ (let us call such polynomial “good”) that encodes this problem. The reduction we showed above works as long as we can construct such “good” polynomial for a problem. Therefore, a new recipe, which was explicitly formulated in [DLW20] for proving average-case (here “average-case” means Erdős–Rényi random input model) fine-grained hardness for a problem $L:\{0,1\}^n\to\mathbf{Z}_{\ge 0}\cap \textrm{poly}(n)$ in P, is

1. Construct a “good” polynomial $f_{L}$ on $\mathbf{F}_p^n$, where $p=\textrm{poly}(n)$, such that $f_{L}(x)=L(x)$ for all $x\in\{0,1\}^n$.

Short and sweet.

In the final post, I will present another instantiation of this new recipe.

Acknowledgements. I would like to thank my quals committee — Aviad Rubinstein, Tselil Schramm, Li-Yang Tan for valuable feedback to my quals talk.