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.
