Georgia Institute of Technology College of Sciences

In 2001, Fishburn, Tanenbaum, and Trenk published a series of two papers that introduced the notions of linear and weak discrepancy of a partially ordered set or poset. Linear discrepancy for a poset is the least k such that for any ordering of the points in the poset there is a pair of incomparable points at least distance k away in the ordering. Weak discrepancy is similar to linear discrepancy except that the distance is observed over weak labelings (i.e. two points can have the same label if they are incomparable, but order is still preserved). My thesis gives a variety of results pertaining to these properties and other forms of discrepancy in posets.

A single round soap bubble provides the least-area way to enclose a given volume. How does the solution change if space is given some density like r^2 or e^{-r^2} that weights both area and volume? There has been much recent progress by undergraduates. Such densities appear prominently in Perelman's paper proving the Poincare Conjecture. No prerequisites, undergraduates welcome.

Santosh Vempala and I have been exploring an intriguing new approach to convex optimization. Intuition about first-order interior point methods tells us that a main impediment to quickly finding an inside track to optimal is that a convex body's boundary can get in one's way in so many directions from so many places. If the surface of a convex body is made to be perfectly reflecting then from every interior vantage point it essentially disappears. Wondering about what this might mean for designing a new type of first-order interior point method, a preliminary analysis offers a surprising and suggestive result. Scale a convex body a sufficient amount in the direction of optimization. Mirror its surface and look directly upwards from anywhere. Then, in the distance, you will see a point that is as close as desired to optimal. We wouldn't recommend a direct implementation, since it doesn't work in practice. However, by trial and error we have developed a new algorithm for convex optimization, which we are calling Reflex. Reflex alternates greedy random reflecting steps, that can get stuck in narrow reflecting corridors, with simply-biased random reflecting steps that escape. We have early experimental experience using a first implementation of Reflex, implemented in Matlab, solving LP's (can be faster than Matlab's linprog), SDP's (dense with several thousand variables), quadratic cone problems, and some standard NETLIB problems.

We will have a chance to spend some time together to discuss issues of relevance to the Graduate Program. Sort of like a "Town Hall Meeting" of the graduate students and the graduate coordinator. There are some things that I need to communicate to all of you, but the format is otherwise unstructured, and I am seeking suggestions on things which you would like to see addressed. So, please send me comments on things which you would like to see discussed and I will do my best to get ready for them. Thanks, Luca Dieci.