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