Tight hardness of the non-commutative Grothendieck problem

Oded Regev
New York University
March 16, 2015
We prove that for any $\epsilon > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \epsilon$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $\ell_2$ into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates. The talk does not assume familiarity with the Grothendieck problem. Joint work with Jop Briet and Rishi Saket.

$A^1$ curves on quasi-projective varieties

Qile Chen
Columbia University
March 17, 2015
In this talk, I will present the recent joint work with Yi Zhu on $A^1$-connectedness for quasi-projective varieties. The theory of $A^1$-connectedness for quasi-projective varieties is an analogue of rationally connectedness for projective varieties. To study curves on a quasi-projective variety $U$, we compactify $U$ by a log smooth pair $(X,D)$. Using the theory of stable log maps to $(X,D)$, we were able to produce $A^1$ curves on $U$ from degeneration. This provides many interesting examples of $A^1$-connected varieties.