By now, it is known that integrality gaps for the standard Unique Games SDP (see the paper of Khot and Vishnoi or Section 5.2 of this post) can be used to obtain integrality gaps for many other optimization problems, and often for very strong SDPs coming from various methods of SDP tightening; see, for instance, the paper of Raghavendra and Steurer.

Problematically, the Khot-Vishnoi gap is rather inefficient: To achieve the optimal gap for Unique Games with alphabet size , one needs an instance of size . As far as I know, there is no obstacle to achieving a gap instance where the number of variables is only .

** The Walsh-Hadamard code **

The Khot-Vishnoi construction is based on the Hadamard code.

(See Section 5.2 here for a complete description.) If we use to denote the Hilbert space of real-valued functions , then the Walsh-Hadamard basis of is the set of functions of the form

where .

Of course, for two such sets , we have the orthogonality relations,

In their construction, the variables are essentially all functions of the form , of which there are , while there are only basis elements which act as the alphabet for the underlying Unique Games instance. This is what leads to the exponential relationship between the number of variables and the label size.

** A PSD lifting question **

In an effort to improve this dependence, one could start with a much larger set of *nearly orthogonal* vectors, and then somehow lift them to a higher-dimensional space where they would become orthogonal. In order for the value of the SDP not to blow up, it would be necessary that this map has some kind of Lipschitz property. We are thus led to the following (possibly naïve) question.

Let be the smallest number such that the following holds. (Here, denotes the -dimensional unit sphere and denotes the unit-sphere of .)

There exists a map such that and whenever satisfy , we have .

(Recall that .)

One can show that

by randomly partitioning so that all vectors satisfying end up in different sets of the partition, and then mapping all the points in a set to a different orthogonal vector.

My question is simply: Is a better dependence on possible? Can one rule out that could be independent of ? Note that any solution which randomly maps points to orthogonal vectors must incur such a blowup (this is essentially rounding the SDP to an integral solution).

### Like this:

Like Loading...

*Related*

This may be a proof that the Lipschitz constant must depend on .

Call a function positive definite on if for every and every Gram matrix of points on , the matrix is positive semi-definite.

A map can be assumed to come from a positive definite function on , in the sense that for all . This should follow by symmetrizing by isometries of .

Specifically, we redefine by the direct integral , where the integral is over the orthogonal group . I believe this step can be done, though I didn’t check the details carefully.

Next, consider a sequence of maps positive definite on . Passing to a subsequence, they converge pointwise to a function positive definite on the Hilbert sphere . Any such function must be analytic in the open interval , thanks to a result of Christensen and Ressel

http://www.ams.org/journals/tran/1978-243-00/S0002-9947-1978-0502895-2/S0002-9947-1978-0502895-2.pdf.

The orthogonality assumption about (and hence ) implies the limit function vanishes identically on . Hence the sequence of maps cannot share a common Lipschitz constant independent of dimension .

The drawback of this proof is the lack of an effective lowerbound on the dependence.

Comment by siuon — March 28, 2011 @ 4:48 pm

Hi, this certainly appears to be a correct proof that as , and the final conclusion about analycity of follows directly from Schoenberg’s characterization. Very nice.

I suspect that a quantitative bound can be obtained from the characterization for positive definite functions on ; see here.

Comment by James Lee — April 1, 2011 @ 4:34 pm

[...] On Chan solved the PSD Lifting question in the comments of the post. Since then, the invention of the short code gave a much more [...]

Pingback by Open question recap | tcs math - some mathematics of theoretical computer science — February 25, 2013 @ 12:28 pm