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