Mathematics Colloquium

Friday, October 4, 1996, 4:00pm

102 Bradley Hall

Professor Sue Whitesides

School of Computer Science

McGill University

speaks on

The Logic Engine Approach to Geometric Lower Bounds

Abstract.We present a simple mechanical computer, called a _logic engine_, which solves instances of the Not-All-Equal 3-Satisfiability problem. Then we show how this mechanical device can be used as a powerful mental image to devise NP-hardness results for a variety of geometric graph embedding problems. The talk will be self-contained.
All are welcome.

Tea. High tea will be served at 3:30pm in the Lounge.
Emmy's. Certain refreshments will be available at the Emmy's after the talk.
Host. Bob Norman is the host. Anybody who is interested in having dinner with the speaker should contact Bob at 646-2762.