Computer Science Talks and Events

Wednesday, April 6, 2016

Matt Ginsberg (aka Dr. Fill), Connected Signals

Dr. Fill: Crosswords and An Implemented Solver for Singly Weighted CSPs

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 is 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 was the CEO of the company from its formation until early 2014 and is currently its chairman.

Ginsberg is also the chairman and CEO of Connected Signals, Inc., a company focusing the on use of real-time traffic and signal information to improve driver safety, fuel efficiency, and the driving experience generally.

Ginsberg is the author of approximately 100 academic publications in the area of artificial intelligence.

4:00 pm in Seeley Mudd 206 with refreshments in Seeley Mudd 208 at 3:30 pm


Friday, April 8, 2016

Dr Dimitrije Kostic, Laboratory for Telecommunications Science, University of Maryland

An Introduction to the Enigma and the Cryptanalysis Against It

Abstract: The Enigma cipher machine was a series of encryption devices used before and during WWII.  The Enigma had an enormous key space, one that the Nazis were sure the Allies would never be able to exhaust over, and because of this the Nazis were totally confident of the device's security and used it to communicate their most sensitive messages.  But the Allies--a team of Polish cryptanalysts before the war, and the British cryptanalysts at Bletchley Park during the war--were able to devise an efficient attack on Enigma, one that produced a gold mine of military intelligence that gave the Allies an enormous advantage and, by some estimates, shortened the war by two years.  Some of these events were dramatized in the recent film The Imitation Game.

This talk will begin with a survey of the major developments in cryptology over the last 2000 years that informed the design of the Enigma.  We will then delve into the details of how the Enigma worked and how cryptanalysis was able to overcome the seemingly insurmountable obstacles to attacking it.  Most of the talk should be accessible to a lay audience, but some of the details of the cryptanalysis will require a basic understanding of the symmetric group to understand fully.

4:00 pm in Seeley Mudd 206 with refreshments in Seeley Mudd 208 at 3:30 pm