Coauthor: Aharon Ben-Tal and Arkadi Nemirovski
Title: The Matrix Cube Theorem and some Extensions.

The Matrix Cube Problem consists of finding out whether or not all matrices in a "cube of matrices" are positive semidefinite or not. The problem is NP-hard, but admits a tractable approximation. The corresponding theorem is due to Ben-Tal and Nemirovski (2001) and has important applications in Combinatorial Optimization and Control Theory (Stability analysis). As such it has inherent relations with the well known work of Goemans and Williamson on the MAXCUT problem, and of Nesterov on Quadratic Optimization over the unit cube. We discuss the theorem, as well as some interesting extensions to the complex case.