Friday, October 4, 1996, 4:00pm
102 Bradley Hall
Professor Sue Whitesides
School of Computer Science
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
Host. Bob Norman is the host. Anybody who is interested in having dinner
with the speaker should contact Bob at 646-2762.