CS Distinguished Lecture Series

Dr. David S. Johnson
At&T Labs - Research
Florham Park, NJTitle: Compressing Rectilinear Pictures and Minimizing Access Control ListsAbstract: We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in common graphics software packages. Here the goal is to create a colored rectilinear pattern within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Rectangle Rule List (RRL) minimization is the problem of finding the shortest list of rules needed to create a given pattern. ACL minimization is a restricted version of this problem where the set of allowed rectangles must correspond to pairs of IP address prefixes. In this talk I'll summarize some recent combinatorial and algorithmic results we have obtained for these two problems.Biography: David S. Johnson is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and Optimization Department of AT & T Labs Research. Johnson graduated summa cum laude from Amherst College in 1967, then earned his S.M. from MIT in 1968 and his Ph.D. from MIT in 1973. All three of his degrees are in mathematics. He is the coauthor of Computers and Intractability: A Guide to the Theory of NP-Completeness (ISBN 0-7167-1045-5)Hosted by: Prof. David Kempe

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Nancy Levien