marina@ai.toronto.edu (Marina Haloulos) (07/22/88)
THEORY SEMINAR Monday, July 25, 1988 11 am - 12 (noon) SF1101 Shai Ben-David The Technion Hiafa, Israel "On the Theory of Average Case Complexity" Average Case Complexity is concerned with pairs <L,M> where L is a subset of strings and M is a probability distribution on strings. The complexity of such a pair is a weighted average of the running time (or space) of an optimal machine for recognizing L. An abstract Average Case Complexity theory was initiated by Levin. This talk will survey a collection of results in this theory. These results indicate that theory of Average Case Complexity is quite similar to that of the classical worst-case complexity. This is a joint work with Benny Chor, Oded Goldreich and Mike Luby.