Speaker: David Johnson, AT&T Labs - Research Time: Wednesday 12-1pm Place: NSH 1507 Title: Compressing Rectilinear Pictures, with Applications to the Internet Abstract: We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers. This model is a generalization of one previously studied in the context of rectilinear picture compression. It embodies an optimization problem that arises when drawing figures using common software packages such as Excel and Xfig. Here the goal is to create a colored rectilinear pattern within an initially white square canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Motivated by the ACL application, we study the special case in which all rectangles must be strips that extend either the full length or the full height of the canvas. We provide several equivalent characterizations of the patterns achievable in this special case and present a polynomial-time algorithm for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also bound the improvement one can obtain by using arbitrary rectangles in the construction of such patterns, and analyze heuristics for the case of general patterns. This is joint work with David Applegate, Gruia Calinescu, Howard Karloff, Katrina Ligett, and Jia Wang.