(Here is the webpage from Fall 2002.)
| Feb 5 | Topic: Stability of multicommodity packet
routing A description of the problem plus suggested reading by David Kempe is here. paper1, paper2 And my writeup of the dual-based invariant mentioned by David is here. |
| Feb 12 | More discussion on packet routing. |
| Feb 19 |
Ara Hayrapetyan Decidability and ground rewriting systems Confluence or Church Rosser property has been well studied in the context of functional languages and their extensions for many decades. The property states that the order of evaluating or reducing a given expression is insignificant and implies that if an expression evaluates to an irreducible normal form, then this normal form must be unique. Church himself was the first to show that Lambda-calculus is confluent. Yet the problem proved harder in other domains. We will investigate the problem in the domain of equational programming languages or rewrite systems, which are often used in theorem provers. The general confluence problem in this context has been shown undecidable long time ago, yet for an interesting subclass of rewrite systems - ground rewrite systems, which are rewrite systems where no variables are allowed - the problem was shown decidable around 15 years ago. The algorithm given at the time was EXPTIME and the exact complexity of confluence for ground rewrite systems had been unknown since. Around a year or two ago a polynomial time algorithm was finally given for this problem and the result was published in FOCS 2001. |
| Feb 26 | Martin Pal Noisy Circulator Random stuff from the paper by Itai Benjamini and Laszlo Lovasz "Global information from local observation", FOCS 2002. |
| Mar 5 | BOOM (no TDG) |
| Mar 12 | Alex Slivkins Title: Edge-Disjoint Paths on Directed Acyclic Graphs This problem is NP-complete; there is an O(m^k) algorithm, where m=#edges and k=#paths. Can we do better than that? I recently proved that (modulo some complexity-theoretic assumptions) there is no algorithm with running time O(f(k)*n^c). Such algorithms are called "fixed-parameter tractable" (FPT). To argue that there is no FPT algorithm, one uses reductions similar to those for NP-hardness. I'll explain briefly how it works, then talk about my proof. |
| Mar 19 | Spring Break |
| Mar 26 | Zoya Svitkina Minimum weight triangulation (MWT) Given a set of points in the plane, a triangulation is a maximal set of non-intersecting line segments connecting the points. MWT is a triangulation that has minimum sum of lengths of all the edges. The problem of finding a MWT is not known either to be in P or to be NP-hard. I will talk about progress that has been made in both directions. For example, there is a polynomial-time algorithm that finds big, usually connected subsets of MWT. On the other hand, some closely related problems are NP-complete. |
| Apr 2 | |
| Apr 9 | Martin Pál Cost Sharing What it is, basic properties we'd like to have, examples, and some open problems. |
| Apr 16 | Mark Sandler SVD decomposition My talk will be about SVD decomposition. I'll start with basic definitions and properties of SVD, and then will talk about fast approximation algorithm from Frank's paper "Fast Computation of Low Rank Matrix Approximations". If time permits I might also talk a little bit about L2 norm and why it is not always very good norm for recovering linear structure. |
| Apr 23 | NO TDG -- David Williamson iss giving an OR colloquium at this time. |
| Apr 30 | Aaron Archer Suppose you have a coin with heads probability p. You do not know what p is, but you do know that p lies in the interval [0,1/2]. Having access only to this coin and a random number generator that gives iid uniform[0,1] samples, how can you simulate a coin with heads probability exactly 2p? Come listen to find out the surprising answer. I'll be presenting the paper "A Bernoulli Factory," by Keane and O'Brien. |
| May 7 | Anirban Dasgupta |
| May 14 | Hubie Chen |