Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsrgv.UUCP
Path: utzoo!utcsrgv!voula
From: voula@utcsrgv.UUCP (Voula Vanneli)
Newsgroups: ont.events
Subject: Theoret.Aspects Sem.-Lower Bound Argu.for Rand.Acc.Mach.
Message-ID: <727@utcsrgv.UUCP>
Date: Fri, 1-Feb-85 13:23:54 EST
Article-I.D.: utcsrgv.727
Posted: Fri Feb  1 13:23:54 1985
Date-Received: Fri, 1-Feb-85 13:27:53 EST
Distribution: ont
Organization: CSRI, University of Toronto
Lines: 20

Theoretical Aspects Seminar - Thursday, February 14, 4 p.m.,
SF 1105
                     Dr. Wolfgang Maass
             University of Illinois at Chicago

     "Lower Bound Arguments for Random Access Machines"

Abstract:  We prove optimal nonlinear lower bounds on random
access machines for two decision problems (Element Distinct-
ness and a pattern matching problem).  The arguments involve
finitary  versions  of  two concepts from mathematical logic
(order indiscernables and inaccessible numbers).





                      February 1, 1985