Informatics Seminar (Perspective in Informatics 4B) 2011 - 2012

January 20 (Fri), 14:45 - 16:45 (Special seminar, 2 talks)

First Talk: 14:45 - 15:45

Title: Bin Packing: From Theory to Experiment and Back Again
Speaker: David S. Johnson (AT&T Labs Research)
Abstract: In the bin packing problem, one is given a list of 1-dimensional items and asked to pack them into a minimum number of unit-capacity bins. This was one of the first NP-hard problems to be studied from the "approximation algorithm" point of view, and over the years it has served as a laboratory for the study of new questions about approximation algorithms and the development of new techniques for their analysis. In this talk I present a brief survey of this history, highlighting the many surprising average case behavior results that have been obtained. Several of these surprises were first revealed by experimentation, which led to conjectures and then to proofs, and I will describe this interplay between experimentation and theory. I'll also highlight some as-yet-unproven conjectures suggested by the experimental data.

Title: Algorithms for Circuits and Circuits for Algorithms
Speaker: Ryan Williams (Stanford University)
Abstract: Over the years, strong connections have been developed between the existence of non-trivial circuit-analysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies a simple property (such as computing the all-zeroes function) can be used to prove limitations on that circuit class, provided the algorithms run slightly faster than exhaustive search. More precisely, a non-trivial SAT algorithm for a circuit class can be used to find functions computable in nondeterministic exponential time that cannot be computed by that circuit class. Informally, this connection can be interpreted as saying "good algorithms for circuits imply there are no good circuits for some algorithms." This talk will explore the ideas behind this theme, and review what we have learned so far.