Noam Livne

In 1984 Levin put forward a suggestion for a theory of {\em average

case complexity}. In this theory a problem, called a {\em

distributional problem}, is defined as a pair consisting of a

decision problem and a probability distribution over the instances.

Introducing adequate notions of simple distributions and average

more >>>