### Polynomial time guarantees for the Burer-Monteiro method

- Diego Cifuentes, Mathematics, MIT
- Monday, February 24, 3-4 p.m., Location: Olney 430

The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in Y, where Y is an n×p matrix such that X = YYT. We show that this method can solve SDPs in polynomial time in an smoothed analysis setting. More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints. We show that if $p\geq\sqrt{(2+2\eta)m}}$, where $m$ is the number of constraints and $\eta>0$ is any fixed constant, then the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. Our bound on $p$ approaches the celebrated Barvinok-Pataki bound in the limit as $\eta$ goes to zero, beneath which it is known that the nonconvex program can be suboptimal.

### Spectral graph theory in quantum communication

- Gabor Lippner, Northeastern University
- Monday, March 2, 4-5 p.m., Location: Olney 430

Physically transmitting quantum information is an important building block of any quantum computer. A possible method to accomplish this is via a "quantum wire", that is, a network of interconnected (coupled) quantum particles. Finding network structures that propagate quantum information efficiently turns out to be very challenging. In this talk I will explain the relevance of spectral graph theory to this problem, and outline some recent results as well as some open problems. Joint work with Mark Kempton, and in part with Shing-Tung Yau, Or Eisenberg, and Whitney Drazen.

### The following seminars have been canceled:

- Mark Lyon, Department of Mathematics and Statistics, University of New Hampshire
- Monday, March 23, 4-5 p.m., Location: Olney 430

- Lam Pham, Brandeis University
- Monday, March 30, 4-5 p.m., Location: Olney 430

- Rubén Campoy, Mathematics, UMass Lowell
- Monday, April 6, 4-5 p.m., Location: Olney 430

- Belleh Fontem, Manning School of Business, UMass Lowell
- Monday, April 13, 4-5 p.m., Location: Olney 430

- Victor Churchill, Dartmouth College
- Monday, April 27, 4-5 p.m., Location: Olney 430