Continuing our previous discussion, I will show another application of the new recipe described in the previous post (i.e., constructing a “good” polynomial for a problem of interest), which will establish average-case hardness of a problem related to the orthogonal vector (OV) problem. (Recall the OV problem: Given , , where each for , decide if there are such that . The reader can look up the worst-case hardness of the OV problem in the first post of the series.)

The motivating question is can we show average-case hardness for counting the number of orthogonal pairs in the OV problem by constructing a “good” polynomial? (One motivation is that such average-case hardness result could serve as the source of reductions for proving average-case hardness for many other problems, because OV is a main source of fine-grained hardness.) There is a good reason to believe the answer is no. Specifically, an -time algorithm for counting orthogonal pairs for average-case OV instances (here “average-case” is Erdős–Rényi random input model, and is a constant that depends on the parameter of the input model) was given in [DLW20], while constructing a “good” polynomial would prove average-case hardness for any constant assuming randomized SETH. This indicates that sometimes constructing a “good” polynomial might be a little too ambitious goal.

Instead, can we first come up with a nice combinatorial problem that encodes OV on a slightly larger binary input space and then construct a “good” polynomial for counting solutions of this combinatorial problem? (The motivation is that since this combinatorial problems encodes OV, it is at least as hard as OV for worst case, and moreover, if we can construct a “good” polynomial for counting solutions of this combinatorial problem, by the new recipe in the previous post, counting solutions of this combinatorial problem for average case is (almost) as hard as that for worst case. Therefore, counting solutions of this combinatorial problem for average case is at least as hard as OV for worst case. More importantly, this combinatorial problem could serve as the source of reductions thanks to its combinatorial structure.) The factored OV problem introduced in [DLW20] gives a positive answer to this question. Analogously, they proposed factored variants for many other flagship fine-grained hard problems. By reductions to these factored problems, they managed to prove average-case fine-grained hardness for many natural combinatorial problems such as counting regular expression matchings (the featured image of this post is the web of reductions in their paper).

Next, for the purpose of exposition, I briefly sketch the high-level idea behind the factored OV problem (without even explicitly describing its combinatorial interpretation, since I will not show any reduction from this problem).

Counting solutions for factored OV. Given an OV instance for (actually, would also work, and the choice here is for simplicity), we encode as ,
where represents the subvector (block) of from the -th to the -th coordinate, and is the long code encoding (specifically, maps a -dimensional binary vector to a -dimensional vector binary vector of which all the coordinates are zero except the coordinate indexed by ). Namely, is the concatenation of the long code encoding of each block of , and thus, , and for our choice of , we have that . Therefore, by taking such encoding for the vectors in the OV instance, we blow up the size of input (and hence weaken the worst-case hardness of OV) very mildly.

The key advantage of such encoding is that the indicator function (which outputs if the two vectors are orthogonal and otherwise) can be represented as the sum of degree- monomials, of which the variables are the coordinates of and . Indeed, we can first enumerate all the orthogonal pairs of vectors , and we check whether has value at coordinate , and has value at coordinate , by taking product of these two coordinates, and then, we take the sum of all the products.

Using this approach, for each , for each , we get a degree- polynomial that computes on input and . The product of these polynomials obviously computes , and moreover, this product is a -partite polynomial (-partite polynomial is defined in the previous post), where each part corresponds to the coordinates of the long code encoding of a block (subvector) of or . If we sum up these -partite polynomials for all pairs , we get a -partite polynomial that precisely counts orthogonal pairs for the OV instance. We can let the field size of this polynomial be a prime ( is a trivial upper bound of the number of orthogonal pairs) such that the output of this polynomial is indeed the number of orthogonal pairs.

Notice that (i) Since the encoding only blows up the input size mildly, the worst-case hardness of OV (almost) carries over to evaluating this polynomial. (ii) Since , the -partite polynomial is a “good” polynomial (defined in the previous post). It follows from our new recipe in the previous post that evaluating this polynomial on binary input for average case (here “average case” means Erdős–Rényi random input model) is (almost) as hard as worst case. (iii) Last but not least, evaluating this polynomial on any (not just for some ) can be interpreted as counting solutions for a combinatorial problem, which is the factored OV problem in [DLW20]. As I mentioned earlier, I will not explain the combinatorial interpretation in details. The takeaway is that counting solutions of such factored problem is average-case fine-grained hard, and its combinatorial structure allows possible reductions to other natural combinatorial problems.

Finally, I mention two broad research directions in this area: (i) design cryptographic primitives, e.g., one-way functions, based on these fine-grained average-case hardness results (or show complexity barriers) and (ii) prove fine-grained average-case hardness for decision problems (or design more efficient algorithms).

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