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


2 Answers 2


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)


The bounded post correspondence problem is complete for RNP (Randomized NP). Therefore, it is believed to be hard on average over uniformly random distributions of inputs.

Y. Gurevich, Average case completeness, J. Comp. Sys. Sci., 42 (3): 346–398, 1991


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.