Theoretical Computer Science

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?

Solution

The assumptions often used in crypto are a form of average-case complexity assumptions, such as hardness of factoring or discrete log in various groups.

Many lattice problems used for strong hardness guarantees for lattice based cryptography are qualitatively somewhat different than the factoring/discrete log based cryptographic assumptions.

The development of indistinguishability obfuscation has also introduced a number of novel average case hardness assumptions.

Often times average case complexity is used in the study of data structures for upper bounds (eg., of hash tables), but there are also some useful lower bounds. For example, the worst case \$\Omega(n \log n)\$ lower bound on sorting can be generalized to the average case, and to randomized algorithms as well (eg., see these lecture notes)