Newsgroups: ut.theory
Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!marina
From: marina@ai.toronto.edu (Marina Haloulos)
Subject: SEMINAR ANNOUNCEMENT
Message-ID: <88Jul22.135635edt.644@neat.ai.toronto.edu>
Date: Fri, 22 Jul 88 12:36:32 EDT


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.