CS Colloquium
November 15, 2012
4:00 p.m., AKW 200

Refreshments will be available at 3:45

Host: Drew McDermott

Sign up to meet with speaker

Title: Dr. Fill: Crosswords and An Implemented Solver for Singly Weighted CSPs
Speaker: Matt Ginsberg, CEO, On Time Systems, Inc.

Abstract: We describe and demonstrate Dr.Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr.Fill works by converting crosswords to weighted CSPs, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr.Filll's performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top hundred or so crossword solvers in the world.

Bio: 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 remained at CIRL until 1998, when CIRL spun off On Time Systems, a commercial entity focusing on scheduling and routing technology. Ginsberg has been the CEO of the company since its formation and is currently its chairman as well.

Ginsberg is also the chairman and CEO of Green Driver, Inc., a sister company to On Time Systems that focuses on using real-time traffic and signal information to provide more fuel-efficient routes to drivers.

Ginsberg's present research interests focus on constraint satisfaction. He is the author of numerous publications in this area, 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, and the author of Dr. Fill, a crossword-solving program that made national news by participating in the American Crossword Puzzle Tournament in March of 2012.