<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.3020" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=845221318-23012007>Satyen Kale will present his preFPO on Tuesday January
30 at 1PM in </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=845221318-23012007>Room 402. The members of his committee are:
Sanjeev Arora, advisor; </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=845221318-23012007>Moses Charikar and Rob Schapire, readers; Bernard
Chazelle and Boaz</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=845221318-23012007>Barak, nonreaders. Everyone is invited to attend
his talk. His abstract </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=845221318-23012007>follows below.</SPAN></FONT></DIV><BR>
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<BR>Title: <SPAN style="TEXT-DECORATION: underline">Efficient Algorithms using
the Multiplicative Weights Update method</SPAN><BR><BR>Algorithms based on
convex optimization, especially linear and semidefinite<BR>programming, are
ubiquitous in Computer Science. While there are polynomial<BR>time algorithms
known to solve such problems, quite often the running time of <BR>these
algorithms is very high. Designing simpler and more efficient algorithms<BR>is
important for practical impact.<BR><BR>In my talk, I will describe
applications of the Multiplicative Weights Update<BR>method in the design of
efficient algorithms for various optimization problems. <BR>This method, which
was repeatedly discovered in quite diverse fields, is an<BR>algorithmic
technique which maintains a distribution on a certain set of<BR>interest, and
updates it iteratively by multiplying the probability mass of <BR>elements by
suitably chosen factors based on the distribution.<BR><BR>The central result of
my thesis is a generalization of the method to the setting of<BR>symmetric
matrices rather than real numbers. I will describe the following
<BR>applications of the resulting Matrix Multiplicative Weights
algorithm:<BR> 1. The first truly general, combinatorial, primal-dual
method for designing<BR> efficient algorithms for semidefinite
programming. Using these techniques, we <BR> obtain significantly faster
algorithms for obtaining O(sqrt{log n})<BR> approximations to various
graph partitioning problems, such as Sparsest<BR> Cut, Balanced Separator
in both directed and undirected weighted graphs, <BR> and the Min UnCut
problem.<BR><BR> 2. An O*(n^3) time derandomization of the Alon-Roichman
construction of<BR> expanders using Cayley graphs.<BR><BR> 3. An
O*(n^3) time deterministic O(log n) approximation algorithm for the <BR>
quantum hypergraph covering problem.<BR><BR> 4. A simpler proof of a
result of Aaronson that the gamma-fat-shattering <BR> dimension of quantum
states on n qubits is O(n/gamma^2).<BR><BR>I will also briefly mention the
following algorithmic applications of the classical <BR>Multiplicative Weights
Update method:<BR> 1. Fast algorithms for approximately solving several
families of semidefinite<BR> programs, which beat interior point methods.
<BR><BR> 2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in
O*(n^2) time. </DIV></BODY></HTML>