Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)
Revenge of the Algebraists
Matt Ginsberg, On Time Systems, Inc.
April 18, 2005, 4:15PM
TCSeq 201
http://graphics.stanford.edu/ba-colloquium/
Abstract
The last ten years have seen a remarkable increase in the use of
general-purpose methods to solve problems of practical interest.
Boolean satisfiability ("SAT") engines have become the technique of
choice in problems ranging from microprocessor verification to
planning. In this talk, we make two related points:
- In the fullness of time, general-purpose methods will inevitably
outperform specialized ones. People working on SAT engines will
take over the world.
- Group-theoretic techniques can be used to greatly extend the
theoretical reach of SAT engines, enabling them to be applied to a
far wider range of problems than previously without sacrificing the
performance gains that have been achieved over the past decade.
The talk covers our reasons for believing (1) and the technical ideas
underlying (2). We also present performance results for an
implemented SAT engine showing polynomial scaling on problems known to
be exponentially difficult for previous methods.
About the Speaker
Matthew L. Ginsberg received his doctorate in mathematics from Oxford
in 1980 at the age of 24. He remained on the faculty in Oxford until
1983, doing research in mathematical physics and computer science;
during this period, he wrote a program that was used successfully to
trade stock and stock options on Wall Street.
Ginsberg's continuing interest in artificial intelligence brought him
to Stanford in late 1983, where he remained for nine years. He then
went on to found CIRL, the computational intelligence research
laboratory at the University of Oregon, which he directed until 1996.
He currently remains on the faculty at CIRL and is the Chief Executive
Officer of On Time Systems, a CIRL spinoff focusing on scheduling and
routing technology.
Ginsberg's present research interests include constraint satisfaction
and scheduling. He is the author of numerous publications in these
areas, the editor of "Readings in Nonmonotonic Reasoning," and the
author of "Essentials of Artificial Intelligence," both published by
Morgan Kaufmann. He is also the author of the bridge-playing program
GIB, which made international news by finishing 12th in the world
bridge championships in Lille, France.
Contact: bac-coordinators@cs.stanford.edu
Back to the Colloquium Page