I recently finished my qualifying exam for which I surveyed worst-case to average-case reductions for problems in NP. As part of my survey, I reviewed recent results on average-case hardness in P (a.k.a. average-case fine-grained hardness). I would like to give an overview of some of these results in a series of blog posts, and I want to start by giving some motivations.

Why do we care about average-case fine-grained hardness?

(i) We hope to explain why we are struggling to find faster algorithms for problems in P such as DNA sequencing even for some random large datasets.

(ii) Average-case hard problems in P is useful to cryptography. For example, constructing one-way functions (i.e., functions that are easy to compute but hard to invert) based on worst-case complexity assumptions such as NP BPP has been a long-standing open question. In this context, “easy” means polynomial-time computable. If we consider “easy” to be computable in time like instead, then a natural alternative question is whether we can construct such one-way functions based on worst-case fine-grained complexity assumptions. Another example is proof of work [DN92]. When a miner tries to mine the cryptocurrency, the miner is asked to solve a random puzzle, that is average-case hard but still tractable, and then the miner needs to prove they have indeed solved the puzzle through efficient protocols. An interesting and more recent follow-up is proof of useful work [BRSV17b], which proposes that instead of wasting computing power on a random puzzle that comes from nowhere, we can first reduce a computational task of practical interest to multiple random puzzles and then ask the miner to solve those puzzles.

The most common approach for proving average-case fine-grained hardness is arguably worst-case to average-case reduction, i.e., reducing an arbitrary instance to a number of random instances of which the distribution is polynomial-time sampable. Before I give concrete examples, I want to describe a general recipe for designing such worst-case to average-case reductions. (Some reader might notice that the step 3 of the recipe is same as the argument for proving computing permanent is self-reducible [L91], which essentially uses local decoding for Reed-Muller codes.)

General recipe for worst-case to average-case reductions:

1. Choose our favorite hard problem in P.
2. Construct a low-degree (degree-) polynomial on such that for all .
3. To solve for worst-case : sample a uniformly random , compute for distinct nonzero using average-case solver (note each is uniformly random), interpolate univariate polynomial using these points, and output which is . (This step can be replaced by decoding algorithms for Reed-Solomon codes to handle larger errors of average-case solver.)
4. (The above steps already show that evaluating for uniformly random inputs is as hard as solving for worst-case input.) If we want to show itself is average-case fine-grained hard, it suffices to give a reduction from computing for back to solving .

Notice that the above general recipe reduces a worst-case instance to random instances at the step 3, and thus, we want to be small (like ) such that it does not blow up the total runtime significantly. Typically, the step 4 would also blow up the runtime, and sometimes it depends on . For all the problems (or the techniques) in this series, I will explicitly quantify the runtime blow-up in the step 4 (if there is any) and explain how small we want to be (if the blow-up depends on ).

Now let us go through a concrete example. Consider one of the flagship problems in fine-grained complexity — orthogonal vector problem (OV): Given , , where each for , decide if there are such that . It is known OV has no -time algorithm for any constant assuming strong exponential-time hypothesis (SETH) [W05], and there is a generalization of OV called -OV that has no -time algorithm under the same assumption [W18].

Polynomial evaluation. Given an OV instance with , we construct a degree- polynomial over for , where denotes the -th coordinate of . Observe that simply enumerates all the pairs of vectors and counts the number of orthogonal pairs for the OV instance, and obviously counting is at least as hard as decision. Using the aforementioned general recipe, it follows immediately that evaluating requires time for average case assuming randomized version of SETH. This result was shown in [BRSV17a], and analogously, they constructed a polynomial for -OV, which implies an average-case time hierarchy assuming randomized SETH.

However, the polynomial evaluation problem is algebraic. Next, let us consider a natural combinatorial problem — counting -cliques in an -vertices graph (for simplicity, think of as a large constant). This problem has worst-case complexity assuming ETH [CHKX06].

Counting -cliques. It was first shown in [GR18] that there is an -time reduction from counting -cliques in any graph to counting -cliques with error probability in some polynomial-time sampable random graph. The proof also follows our general recipe. First, we construct a degree- polynomial over for , where is the adjacency matrix. Observe that counts -cliques by enumerating each size- subset of vertices and checking whether it is a -clique. It remains to work out the step 4 of the general recipe. This was done by a gadget reduction, that runs in time, from evaluating on to counting -cliques in an -vertices graph [GR18].

Although this gadget reduction is nice, I will not explain it here, because later works [BBB19, DLW20] show that if the polynomial constructed at the step 2 has certain structure, then there is a general technique to reduce evaluating this polynomial back to the original problem (at the cost of requiring smaller error probability of average-case solver), which I will discuss in the next post. Finally, let me point out an issue in the previous paragraph — is too large for the gadget reduction to be useful! We need (note is a trivial upper bound of the number of -cliques) such that indeed outputs the number of -cliques, but the gadget reduction takes time, and moreover, we do not know how to find a prime in time. This issue was handled in [GR18] using Chinese remainder theorem. Specifically, we choose many distinct primes ‘s upper bounded by whose product is (the existence of such primes follows from asymptotic distribution of the prime numbers). Then, we apply the whole reduction described so far to evaluating for each and then use Chinese remainder theorem to recover . (We can use Chinese remaindering with errors [GRS99] to handle larger error probability.)

Hopefully, the above examples give you a flavor of worst-case to average-case reductions for fine-grained hard problems. As promised, in the next post, I will continue to discuss the new technique in [BBB19, DLW20], which automatizes the step 4 of the general recipe by requiring more structural properties for the polynomial constructed in the step 2 of the general recipe.

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