I was told of this pioneering work before it was posted, but kept postponing recommending it to a careful reading. Given that a month has elapsed and this has not happened yet, let me comment on this work based on a superficial knowledge of it.
Basically, it shows relatively hard (based on widely-believed fine-grained complexity conjectures) functions in P that have a worst-case to average-case reductions that run in almost linear-time. Hence, under the said conjectures, these functions can be computed on the worst-case in time $p$, for some polynomial $p$, but cannot be computed much faster even just on typical inputs (i.e., in the average-case).
The abstract mentions an (unconditional) average-case hierarchy theorem of Goldmann, Grape, and Hastad (1994), which is obtained by diagonalization, but fails to clearly articulate the advantage of the current work. The point is that the current results (1) are robust under the presence of auxiliary inputs, (2) support various applications that refers to the structure of the computational problem, and (3) do not depend on huge and unspecified constants.
We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL 1994), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.
We prove our hardness results in each case by showing fine-grained reductions from solving one of three problems - namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) - in the worst case to computing our function correctly on a uniformly random input. The conjectured hardness of OV and 3SUM then gives us functions that require $n^{2-o(1)}$ time to compute on average, and that of APSP gives us a function that requires $n^{3-o(1)}$ time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.
Based on the average-case hardness and structural properties of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing fine-grained One-Way Functions. We also show how our reductions make conjectures regarding the worst-case hardness of the problems we reduce from (and consequently the Strong Exponential Time Hypothesis) heuristically falsifiable in a sense similar to that of (Naor, CRYPTO '03).
See ECCC TR17-039.