UTCS Colloquia/AI - Matthew L. Ginsberg/University of Oregon, "Dr. Fill: Crosswords Aren't Just for Humans Any More", PAI 3.14

Contact Name: 
Jenna Whitney
Jan 19, 2012 11:00am - 12:00pm

There is a sign-up schedule for this event that can be found at


Type o

f Talk: UTCS Colloquia/AI

Speaker/Affiliation: Matthew L. Ginsberg/Uni

versity of Oregon

Talk Audience: UTCS Faculty, Grad Students, Underg

rads and Outside Interested Parties

Date/Time: January 19, 2012, 11:

00 a.m.

Location: PAI 3.14

Host: Vladimir Lifschitz

Talk Tit

le: Dr. Fill: Crosswords Aren''t Just for Humans Any More

Talk Abstrac

We describe Dr.Fill, a program that solves American-style crossword

npuzzles. From a technical perspective, Dr.Fill works by converting

swords to weighted CSPs, and then using a variety of novel
techniques to
find a solution. These techniques include generally
applicable heuristic

s for variable and value selection, a variant of
limited discrepancy sea

rch, and postprocessing and partitioning ideas.
Branch and bound is not

used, as it was incompatible with
postprocessing and was determined expe

rimentally to be of little
practical value. Dr.Fill''s performance on cro

sswords from the American
Crossword Puzzle Tournament suggests that it ra

nks among the top fifty
or so crossword solvers in the world.


r Bio:
Matthew L. Ginsberg received his doctorate in mathematics from Oxf

in 1980 at the age of 24. He remained on the faculty in Oxford until

1983, doing research in mathematical physics and computer science;

ring this period, he wrote a program that was used successfully to
stock and stock options on Wall Street.

Ginsberg''s continuing intere

st in artificial intelligence brought him
to Stanford in late 1983, wher

e he remained for nine years. He then
went on to found CIRL, the computa

tional intelligence research
laboratory at the University of Oregon, whi

ch he directed until 1996.
He remained at CIRL until 1998, when CIRL spu

n off On Time Systems, a
commercial entity focusing on scheduling and ro

uting technology.
Ginsberg has been the CEO of the company since its form

ation and is
currently its chairman as well.

Ginsberg is also the ch

airman and CEO of Green Driver, Inc., a sister
company to On Time Syste

ms that focuses on using real-time traffic and
signal information to prov

ide more fuel-efficient routes to drivers.

Ginsberg''s present researc

h interests focus on constraint
satisfaction. He is the author of numerou

s publications in this areas,
the editor of "Readings in Nonmonotonic Re

asoning," and the author of
"Essentials of Artificial Intelligence," bo

th published by Morgan
Kaufmann. He is also the author of the bridge-play

ing 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 will be participating in the American

Crossword Puzzle Tournament in March of 2012.