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