Grothendieck inequality and hyperbolicity (Sebastien Bubeck)

Let me warn you that this open problem is more open ended than the one on Thompson Sampling!

Grothendieck’s inequality and its proof by Gaussian projection give a universal rounding scheme for semidefinite programs. The question is whether there exist a generalization of Grothendieck’s inequality to hyperbolic programs, and what would the rounding scheme look like in this case?

Some readings:

– See section 7 here for a clean description of hyperbolic programming and the associated basic concepts.

– See section 2 here for a simple proof of Grothendieck’s inequality.

– Known connections between hyperbolicity and probability will probably be useful here, see this survey by Robin Pemantle.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s