Amit Agarwal will present his preFPO on Monday May 14 at 3:30PM in Room 302 (note room!). The members of his committee are: Moses Charikar, advisor; Rob Schapire and Sanjeev Khanna (U Penn), readers; Ken Steiglitz and Bob Tarjan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Optimization has emerged as a field of central importance for its practical applications in operations research, physics, chemistry, applied mathematics, and computer science. As our understanding of optimization has deepened, it has emerged that several important optimization problems are difficult to solve exactly in reasonable amount of time, assuming widely believed complexity assumptions. The natural approach in such cases is to obtain approximate solutions. There is a huge body of work towards designing algorithms with provable guarantees about their sub-optimality. In general, two kinds of error estimation techniques have been evolved for such problems: multiplicative and additive. In the study of approximation algorithms one typically looks for multiplicative approximation to problems which are NP-hard. On the other hand, results in the field of online optimization typically have additive errors. The latter work also has connections to machine learning and statistics. I will present three results in the broad area of approximate optimization: (i) The first result is on improved approximation for directed cut problems from joint work with Noga Alon and Moses Charikar. (ii) The second result bridges the field of approximation algorithms and network coding theory. We show that certain integrality gaps studied by the approximation algorithms community are the same as certain parameters in network coding. This is joint work with Moses Charikar. (iii) Finally we present faster algorithms for online optimization with applications to portfolio management. This is based on papers with Elad Hazan, Robert Schapire, Satyen Kale, and Adam Kalai.