The research proposed is concerned with probabilistic concepts arising in the theory of computation on the one hand, and its effect on the understanding of the nature of randomness on the other. The theory of problems with intractable random instances is more subtle than similar worst-case theories. Constructive expanders, coding theory, and other combinatorial and algebraic techniques must be used. An important use of hard-on-average problems is the generation of pseudo-random strings. In contrast, worst-case negative results rarely have applications, while worst-case positive results are hopeless for many easy-on average problems.
