Computer Science Events
CS Tea Talk by Matt Ginsberg
Matt Ginsberg will be giving a talk on "Dr. Fill: Crosswords and An Implemented Solver for Singly Weighted CSPs."
Title and abstract
Dr. Fill: Crosswords and An Implemented Solver for Singly Weighted CSPs
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.
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 improve driver safety, fuel efficiency, and the driving experience generally.
Ginsberg's present research interests focus on constraint satisfaction. He is the author of numerous publications in this 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,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.
Sponsored by Computer Science. Contact: Sue Jandro, x4360