Computer Science/Discrete Mathematics Seminar II
Factorization through L2, Rounding and Duality
Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement:
Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X < infinity), can be written as the composition (A=B.C) of bounded linear operators C mapping X to L2 and B mapping L2 to Y.
Such factorization theorems and their variants (for various choices of normed spaces X and Y) are useful not only in functional analysis (where they were developed to study norms on tensor product spaces X \otimes X), but in several areas of computer science like discrepancy theory, communication complexity, column subset selection and optimization. In this talk I will discuss a generic recipe (using rounding+duality) for proving factorization theorems. My goal is to provide a streamlined exposition of a classical factorization theorem of Grothendieck and time permitting show a new factorization result which has applications to quadratic maximization over convex sets.
Based on recent joint work with Euiwoong Lee and Assaf Naor.