  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, $k$SUM 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''-$3$SUM. We show that
factored-$k$-OV and factored $k$SUM 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...
