Constraint Satisfaction Problems (CSP) can be formulated as tensor optimization problems. So also the interesting planted clique problem. Much about tensors is known to be hard or impossible, But the focus of this talk will be the possible. In particular, we show that the spectral norm of any r-dimensional array (for r fixed) can be approximated to additive error $\varepsilon$ times its Frobenius norm and this is sufficient to solve dense instances of MAX-CSP's as well as a more general class.

 

Joint work with Frieze, de la Vega, Karpinski, Vempala.