SEMINAR ANNOUNCEMENT

Article View: ut.theory

Article #246

#246

From: Marina Haloulos
Date: Fri, 22 Jul 1988 16:36

25 lines
1029 bytes

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.

Technical Details

Message-ID: <88Jul22.135635edt.644@neat.ai.toronto.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!marina

Show Full Headers

Complete Article Headers

Newsgroups: ut.theory
Path: arc1-ca.pugleaf.net!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