Popular average-case complexity assumptions

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)

Solved by user8985 (2,295 )
Dec 15, 2015 at 05:16