New Techniques for Proving Fine-Grained Average-Case Hardness

The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). This paper defines new versions of OV, kSUM and zero-k-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain ``factored'' form. We call them ``factored''-OV, ``factored''-zero-k-clique and ``factored''-3SUM. We show that factored-k-OV and factored kSUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero-k-clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g.~to edit distance, k-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adsera et al. 2019] that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Boix-Adsera et al.'s average-case counting k-cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in k-partite graphs...