
06/18 2:00pm 
zoom 
Guillaume Aubrun Lyon 1 
Entangleability of cones
Given two finitedimensional cones, one can naturally define
their minimal and maximal tensor products. We show that both coincide if
and only if one of the cones is simplexbased, as was conjectured by
Barker (1976). Our proof involves a mix of convex geometry, elementary
algebraic topology, and computations inspired by quantum information
theory (arXiv:1911.09663, joint with Ludovico Lami, Carlos Palazuelos and
Martin Plavala). 

07/02 04:00am 
zoom 
Pravesh Kothari CMU 
The SumofSquares Approach to Clustering Gaussian Mixtures
SumofSquares is a systematic proof system for reasoning about real solutions to systems of multivariate polynomial inequalities over the reals. In the last few years, this proof system has been used to develop a principled method for designing efficient algorithms for averagecase algorithmic problems  problems where the inputs are chosen according to some natural probability distribution. By relying on the relationship between sumofsquares proofs and semidefinite programming, this method reduces designing an efficient algorithm for a given problem to giving a lowdegree sumofsquares certificate of the correctness of a purported solution.
In this talk, I'll give an overview of this method by focusing on two recent works on designing algorithms for the problem of clustering mixtures of k Gaussians in d dimensions:
1) A d^( O(log^2 k) ) time algorithm for clustering mixtures of k Gaussians with spherical covariances that succeeds whenever the mixture is informationtheoretically clusterable. This algorithm relies on using sumofsquares certificates of subgaussian moments.
2) A $d^O(k^(O(k)))$ time algorithm for clustering mixtures of k arbitrary Gaussians that succeeds whenever the mixture is clusterable. This algorithm relies on sumofsquares certificates of hypercontractivity of degree 2 polynomials and anticoncentration of linear projections of Gaussians.
The talk should be accessible to a broad audience and should not require any prior knowledge of the problems/techniques.
The talk is based on joint works with Jacob Steinhardt and Ainesh Bakshi. 