Average-Case Fine-Grained Hardness, Part II

Posted on July 30, 2021 by Junyao Zhao in Uncategorized // 2 Comments

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<p^{(1)},\dots,p^{(k)}<1 (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<j) 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.

2 Trackbacks / Pingbacks

  1. Average-Case Fine-Grained Hardness, Part I – Theory Dish
  2. Average-Case Fine-Grained Hardness, Part III – Theory Dish

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

Copyright © 2023 Create a website or blog at WordPress.com

%d bloggers like this: