[talks] S Sachdeva general exam
Melissa Lawson
mml at CS.Princeton.EDU
Tue May 11 14:17:17 EDT 2010
Sushant Sachdeva will present his research seminar/general exam on Monday May 17 at 2PM
in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar,
and Bernard Chazelle. Everyone is invited to attend his talk and those faculty wishing to remain
for the oral exam following are welcome to do so. His abstract and reading list follow below.
----------------------------------------------------
Title : Parallel Approximation algorithms based on SDPs
Abstract:
We explore the following question: Can the matrix exponential update
method can help us give efficient SDP based parallel approximation
algorithms?
The matrix multiplicative weights method or the matrix exponential
update method, developed by Arora and Kale has proved to be a
successful framework to design faster approximation algorithms based
on solving semidefinite programs (SDP). Very recently, the method has
been used in a work of Jain et al to show that the class of Quantum
Interactive Proofs (QIP) is the same as PSPACE. Their work relies on
using the matrix exponential update method to solve an exponential
sized SDP using a circuit of only polynomial depth.
Aside from being a natural question, the aforementioned result
strongly hints at the possibility of parallel algorithms based on this
method. Luby and Nisan ('93) had shown that (scalar) multiplicative
weights method could be used to approximate packing-covering LP's
(positive LPs) up to (1+eps) in parallel (EREW PRAM). An eventual goal
of the work is to show a matrix analogue of their result.
In this work, we give parallel algorithms for solving the MaxCut SDP
(up to a multiplicative factor of 1+eps) and finding an O(log n)
approximation to balanced separator. Our algorithms require
poly(n/eps) processors and time poly(log n/eps). Using the work of
Steurer, we can also give an efficient parallel algorithm to solve the
'standard sdp' for any CSP.
We will also talk about some results on another problem. In a recent
STOC paper, Lee and Moharrami construct a metric (X,d) such that the
metric (X,sqrt(d)) can be embedded with constant distortion into L_2
but embedding (X,d) into a negative type metric (L_2-squared) requires
distortion at least Omega((log n)^{1/7}). We are able to give a
tighter analysis of their construction and improve the bound to
Omega((log n)^{1/3}).
Joint work with Sanjeev Arora.
Reading list
=========
A. Books:
a. Algorithm Design - Jon Kleinberg, Eva Tardos
b. Complexity theory (Chap. 1-8 (basic complexity), 11 and 22 (PCP
theorem))- Sanjeev Arora, Boaz Barak
B. Papers:
� A combinatorial primal-dual approach to semidefinite
programs - Sanjeev Arora, Satyen Kale
� A parallel approximation algorithm for positive linear
programming - Michael Luby, Noam Nisan
� Fast SDP algorithms for constraint satisfaction
problems- David Steurer
� The multiplicative weights update method: A
meta-algorithm and applications (Survey) - Sanjeev Arora, Elad Hazan,
Satyen Kale
� QIP = PSPACE - Rahul Jain, Zhengfeng Ji, Sarvagya
Upadhyay, John Watrous
� Matrix exponentiated gradient updates for on-line
learning and bregman projections - Koji Tsuda, Gunner Ratsch and
Manfred K. Warmuth
� Fast approximation algorithms for fractional packing
and covering problems - Serge Plotkin, David Schmoys and Eva Tardos
� Online Variance minimization - Manfred K. Warmuth, Dima Kuzmin
� Twice Ramanujan Sparsifiers : Joshua Batson, Daniel
Spielman, Nikhil Srivastava
� An elementary proof of the Restricted Invertibility
Theorem : Daniel Spielman, Nikhil Srivastava
More information about the talks
mailing list