clarke@utcsri.UUCP (09/29/87)
(SF = Sandford Fleming Building, 10 King's College Road) (GB = Galbraith Building, 35 St. George Street) SUMMARY: COMBINATORICS SEMINAR, Monday, October 5, 3 pm SF1102 -- Irith Hartman: "Path Partitions and Independent Sets In Directed Graphs" COLLOQUIUM, Tuesday, October 6, 11 am, SF1105 -- C. Rackoff: "Cryptography: State of the Art" A.I. SEMINAR, Tuesday, October 6, 2 pm, GB244 -- Chuck Rich: "Bread, Frappe and Cake: A Gourmet's Guide to Automated Deduction" GRAPHICS SEMINAR, Tuesday, October 6, 3 pm, GB120 -- Philip K. Robertson: "Displaying images as surfaces - a new approach to the hidden surface problem" -------------------- COMBINATORICS SEMINAR, Monday, October 5, 3 pm SF1102 Professor Irith Hartman Visiting Post-doc Department of Computer Science University of Toronto "Path Partitions and Independent Sets In Directed Graphs" COLLOQUIUM, Tuesday, October 6, 11 am, SF1105 Professor C. Rackoff University of Toronto "Cryptography: State of the Art" The only cryptosystems known to be secure, such as the one-time pad, have a private key as long as the message to be sent. It is possible (although unlikely) that every other system is insecure, and it is even plausable that every currently known system is insecure. The best that we know how to do is to construct systems that can be proven to be secure assuming cer- tain number theory conjectures. Assuming these conjectures are true, we cannot only do traditional cryptography, but we can also construct many wonderful and counterintuitive protocols for other tasks. For example, I can prove to you that a mathematical theorem is true, without giving you any idea of why it is true or any idea of how to prove it. A.I. SEMINAR, Tuesday, October 6, 2 pm, GB244 Professor Chuck Rich MIT AI LAB "Bread, Frappe and Cake: A Gourmet's Guide to Automated Deduction" Cake is the knowledge representation and reasoning system developed as part of the Programmer's Apprentice project. Cake can be thought of as an active database, which performs quick and shallow deductions automatically; it supports both forward-chaining and backward-chaining reasoning. The Cake system has a layered architecture: the kernel of the system, called Bread (for Basic REAsoning Device), is a truth-maintenance system with equality and demons. Built on top of this is Frappe (for FRAmes in a Pro- Positional Engine), which implements a typed logic with special-purpose decision procedures for various algebraic properties of operators (such as commutativity and associativity), sets, partial functions, and structured objects (frames). Only the topmost layer of Cake, which implements the Plan Calculus, is specific to reasoning about programs. This talk will describe the architecture and features of Bread, Frappe, and Cake, including a transcript of a demonstration session. This is joint work with Yishai Feldman. GRAPHICS SEMINAR, Tuesday, October 6, 3 pm, GB120 Professor Philip K. Robertson University of Toronto "Displaying images as surfaces - a new approach to the hidden surface problem" Surface representations allow arbitrarily-valued images (height fields, or terrain models) to be displayed, analysed and manipulated. However, con- ventional parametic and object-oriented graphics techniques are not neces- sarily well suited to handling image data. In particular, processes which involve hidden-surface elimination, such as the generation of 3-D perspec- tive views or surface shadowing, can incurr substantial computational and I/O costs. This seminar will show how spatial transformations can reduce hidden-surface determination to a simple 1-D process, decreasing computa- tional costs significantly and simplifying data I/O requirements. The approach is scan-line in nature, and relies on the separability of transforms, such as the perspective projection, into 1-D operations per- formed on scan-rows or scan-columns of the image. Parallel hardware offers the potential for extremely rapid operation. The approach has the addi- tional advantages that it can be implemented in a severely memory-limited environment, and that it greatly facilitates interpolation, antialiasing and some physical modelling. The more general potential of spatial transformations of this nature in image processing and graphics will also be discussed. -- Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4 (416) 978-4058 {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke