FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
7A

How to Play Unique Games Against a SemiRandom AdversaryIn this paper, we study the average case complexity of the Unique Games problem. We propose a natural semirandom model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1epsilon) satisfiable instance, so then the problem is as hard as in the worst case. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semirandom instances of Unique Games. We present an algorithm that with high probability finds a solution satisfying a (1delta) fraction of all constraints in semirandom instances (we require that the average degree of the graph is Omega(log k)). To this end, we consider a new nonstandard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest. Finally, we study semirandom instances of Unique Games that are at most (1epsilon) satisfiable. We present an algorithm that distinguishes between the case when the instance is a semirandom instance and the case when the instance is an (arbitrary) (1delta)satisfiable instance if epsilon > c delta (for some absolute constant c).

The Grothendieck constant is strictly smaller than Krivine's boundWe prove that $K_G<\frac{\pi}{2\log\left(1+\sqrt{2}\right)}$, where $K_G$ is the Grothendieck constant.

A Parallel Approximation Algorithm for Positive Semidefinite ProgrammingPositive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are nonnegative. We present a parallel algorithm, which given an instance of a positive semidefinite program of size N and an approximation factor eps > 0, runs in (parallel) time poly(1/eps) polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1+eps) to the optimal. Our result generalizes analogous result of Luby and Nisan [1993] for positive linear programs and our algorithm is inspired by their algorithm.

Rounding Semidefinite Programming Hierarchies via Global CorrelationWe show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDPhierarchy based algorithm for Unique Games. Our algorithm matches the performance of the recent algorithm of Arora, Barak and Steurer (FOCS 2010) in the worstcase, but is shown to run in polynomial time on a richer family of instances, thus ruling out more possibilities for hard instances for the Unique Games Conjecture. Specifically, we give a rounding algorithm for $O(r)$ levels of the Lasserre hierarchy that finds a good integral solution as long as, very roughly speaking, the average correlation between vectors in the SDP solution is at least $1/r$. In the case of Unique Games, the latter condition is implied by having at most $r$ large eigenvalues in the constraint graph. This improves upon prior works that required the potentially stronger condition of a bound on the number of eigenvalues in the \emph{label extended graph}. Our algorithm actually requires less than the $n^{O(r)}$ constraints specified by the $r^{th}$ level of the Lasserre hierarchy, and in particular $r$ rounds of our program can be evaluated in time $2^{O(r)}\mathrm{poly}(n)$.

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD ObjectivesWe present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Uniform sparsest cut, Minimum graph bisection, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NPhardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for lowrank approximations of a matrix in Frobenius norm using columns of the matrix.For all the above graph problems, we give an algorithm running in time $n^{O(r/\eps^2)}$ with approximation ratio $\frac{1+\eps}{\min\{1,\lambda_r\}}$, where $\lambda_r$ is the $r$'th smallest eigenvalue of the normalized graph Laplacian $\Lnorm$. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lowerorder terms of the stipulated bound. Our results imply $(1+O(\eps))$ factor approximation in time $n^{O(r^\ast)}$ where $r^\ast$ is the number of eigenvalues of $\Lnorm$ smaller $1\eps$. This perhaps gives some indication as to why even showing mere APXhardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure). For Unique Games, we give a factor $(1+\frac{2+\eps}{\lambda_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/\eps)}$ time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve wellknown integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.