[ont.events] Theoretical Aspects Seminar

eas@utcsrgv.UUCP (Ann Struthers) (01/09/85)

		      THEORETICAL ASPECTS SEMINAR

		      Thursday, January 17, 1984

		4:00 P.M. Sandford Fleming Building 1101


		            Ms. Anna Lubiw

           Ph.D. candidate in the Department of Computer Science
		         University of Toronto

        "Decomposing a Polygonal Region into Convex Quadrilaterals"

eas@utcsrgv.UUCP (Ann Struthers) (01/16/85)

                        THEORETICAL ASPECTS SEMINAR

                        Thursday, January 24, 1985

                            4:00 P.M. SF 1105


			    Mr. Robert Wilber
                        Carnegie-Mellon University
			       Pittsburgh


                           "White Pebbles Help"

Abstract:

The black pebble game is a one player game played on a directed acyclic
graph. Black pebbles are placed on and removed from vertices of the dag
according to rules that model the deterministic evaluation of a straight-
line program. The number of pebbles needed to pebble a dag is equal to 
the number of registers needed to evaluate the corresponding straight-
line program. The black-white pebble game is an extension of the black
pebble game in which white pebbles are used to model nondeterministic
guesses that can be made at any time but must eventually be verified.
The number of pebbles needed to pebble a dag in the black-white pebble 
game is equal to the number of registers needed to evaluate the corres-
ponding straight-line program by a nondeterministic strategy.

I construct a family of dags with vertex in degrees bounded by 2 such
					2
that the nth dag can be pebbled with 0(n ) pebbles in the black-white
pebble game but for which any strategy of the black pebble game requires
   2
w(n ) pebbles. This shows that there are straight-line programs that
can be evaluated nondeterministically with asymptotically less space
than is required by any deterministic evaluation.

voula@utcsrgv.UUCP (Voula Vanneli) (01/31/85)

                     LATE ANNOUNCEMENT



THEORETICAL ASPECTS SEMINAR - Tuesday, February 5,  11  a.m.
in SF 1105
  (SF = Sandford Fleming Building, 10 King's College Road)
          University of Toronto, Toronto, Ontario


                       Silvio Micali
              Laboratory for Computer Science


             How to Get a Proof from the Devil


Abstract:  For some number theoretic languages _L we show how
someone  who  has  enough information (henceforth called the
Devil) can prove to a skeptical man that a string belongs to
_L, without releasing any additional knowledge.




































                      January 30, 1985