[talks] S Kale preFPO

[Melissa M Lawson]

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. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cs.princeton.edu/pipermail/talks/attachments/20070123/d5dc49bd/attachment.htm