Satyen Kale will present his preFPO on Tuesday January 30 at 1PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Rob Schapire, readers; Bernard Chazelle and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. _____ Title: Efficient Algorithms using the Multiplicative Weights Update method Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact. In my talk, I will describe applications of the Multiplicative Weights Update method in the design of efficient algorithms for various optimization problems. This method, which was repeatedly discovered in quite diverse fields, is an algorithmic technique which maintains a distribution on a certain set of interest, and updates it iteratively by multiplying the probability mass of elements by suitably chosen factors based on the distribution. The central result of my thesis is a generalization of the method to the setting of symmetric matrices rather than real numbers. I will describe the following applications of the resulting Matrix Multiplicative Weights algorithm: 1. The first truly general, combinatorial, primal-dual method for designing efficient algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for obtaining O(sqrt{log n}) approximations to various graph partitioning problems, such as Sparsest Cut, Balanced Separator in both directed and undirected weighted graphs, and the Min UnCut problem. 2. An O*(n^3) time derandomization of the Alon-Roichman construction of expanders using Cayley graphs. 3. An O*(n^3) time deterministic O(log n) approximation algorithm for the quantum hypergraph covering problem. 4. A simpler proof of a result of Aaronson that the gamma-fat-shattering dimension of quantum states on n qubits is O(n/gamma^2). I will also briefly mention the following algorithmic applications of the classical Multiplicative Weights Update method: 1. Fast algorithms for approximately solving several families of semidefinite programs, which beat interior point methods. 2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in O*(n^2) time.