Title: A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral CaseSpeaker: Sharat Ibrahimpur Affiliation: University of Waterloo Zoom: Contact Sharat Ibrahimpur
Given a connected undirected graph G on n vertices, and non-negative edge costs c, the 2ECM problem is that of finding a 2-edge connected spanning multisubgraph of G of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of G, gives a lower bound on the optimal cost.
Title: Semidefinite programming representations for separable statesSpeaker: Hamza Fawzi Affiliation: University of Cambridge Zoom: Please email Emma Watson
The set of separable (i.e., non-entangled) bipartite states is a convex set that plays a fundamental role in quantum information theory. The problem of optimizing a linear function on the set of separable states is closely related to polynomial optimization on the sphere. After recalling the sum-of-squares hierarchy for this problem, I will show bounds on the rate of convergence of this SDP hierarchy; and prove that the set of separable states has no SDP representation of finite size.