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. 

Date & Time

November 17, 2020 | 10:30am – 12:30pm

Location

Simonyi Hall 101 and Remote Access - see Zoom link below

Affiliation

Member, School of Mathematics