Average-Case Fine-Grained Hardness, Part II
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 -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
-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 -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
-time reduction from counting
-cliques in any
-vertex graph to counting
-cliques with error probability
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
and
, for any constants
(for our application, these constants will be equal), given independent Bernoulli random variables
, the distribution of
is close to the uniform distribution over
, i.e., the statistical distance is less than
(later when we apply this lemma, we want
to be
, and therefore
). We skip the proof of this lemma which is a nice application of basic Fourier analysis.
As in the previous post, denotes a constructed polynomial that computes the number of
-cliques when the input is an adjacency matrix of a graph. The step 3 of the general recipe from the previous post reduces counting
-cliques for the worst-case graph to evaluating
on
many uniformly random
(recall in the previous post,
is the degree of the polynomial
, and
is
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
in the decomposition lemma to be
such that the sampling scheme succeeds w.h.p. by a few attempts), we can further reduce evaluating
on uniformly random
to evaluating
, where each
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
, then we are done, because evaluating
on the adjacency matrix of an Erdős–Rényi graph is precisely counting
-cliques for Erdős–Rényi graph.
When can we “pull out” the weighted sum for a polynomial ? One answer is when the polynomial is
-partite.
An -variate polynomial
is
-partite if there is a partition of the set of variables
such that
is the sum of monomials in which each monomial contains exactly one variable from each part
(more formally,
for some
).
For -partite polynomial
, it is not hard to show that
(Essentially, because two variables from the same never appear in the same monomial, we can enumerate variables from the same
in the same order.)
Let us think of each as a coordinate of Erdős–Rényi adjacency matrix
, then
is evaluating
on an ensemble of distinct coordinates of
‘s, and such ensemble is obviously Erdős–Rényi as well. Therefore, we have managed to decompose
into sum of
many
‘s where each
denotes an Erdős–Rényi adjacency matrix. In the next paragraph, we will construct a
-partite polynomial
for counting
-cliques, and therefore, we have reduced computing
to computing
many
‘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
, and hence, as long as
, we are good to go.)
Unfortunately, the given in the previous post does not work. Instead, we first reduce counting
-cliques in any graph to counting
-cliques in a
-partite graph, and then we construct a
-partite polynomial
for counting
-cliques in a
-partite graph. Reduction from counting
-cliques in any graph to counting
-cliques in a
-partite graph is standard. Simply consider the tensor product between the original graph and another
-clique. The number of
-cliques in the tensor product graph is exactly
times that in the original graph. Now given the
-paritite graph, let
denote the
-th part of vertices, and let
(for
) denote the adjacency matrix between
and
. Consider the new polynomial
, where
denotes the coordinate that indicates if there is an edge between
. Observe that
counts
-cliques by picking one vertex for each part and checking if these
vertices form a clique. It is indeed
-partite as each
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 -cliques we have used in the entire reduction except for constructing
.
The answer is none! The only part specific to counting -cliques was cooking up a
-partite polynomial for
(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
in P, is
- Construct a “good” polynomial
on
, where
, such that
for all
.
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.
Leave a Reply