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


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: 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.


Back to the Colloquium Page