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).