Title: A Framework for Quadratic Form Maximization over Convex Sets

Vijay Bhattiprolu

Abstract. We investigate the approximability of the following optimization
problem, whose input is an n-by-n matrix A and an origin symmetric convex
set C that is given by a membership oracle: "Maximize the quadratic form as
x ranges over C." 

This is a rich and expressive family of optimization problems; for
different choices of forms A and convex bodies C it includes a diverse
range of interesting combinatorial and continuous optimization problems. To
name some examples, max-cut, Grothendieck's inequality, the non-commutative
Grothendieck inequality, certifying hypercontractivity, small set
expansion, vertex expansion, and the spread constant of a metric, are all
captured by this class. While the literature studied these special cases
using case-specific reasoning, here we develop a general methodology for
treatment of the approximability and inapproximability aspects of these
questions. Time permitting, I will highlight a connection to the
factorization theory of linear operators.