** By Passing UGC:**

**Inapproximability of subspace approximation**

Scribes: Pierre Pansu and Jian Ding

Joint work with Prasad Raghavendra, Rishi Saket and Ji Wu, [GRSW].

There will be unconditional tight hardness results today. They were initially proved assuming UGC.

**1. The problem and background **

Definition 1Subspace approximation.

Input: , points in Euclidean . Output: a -dimensional linear subspace . Objective: Minimize

**Special cases.**

- : Low rank matrix approximation; solvable in polynomial time by Singular Value Decomposition.
- and : radii of point sets.

**Previous results: Algorithmic**

- Polynomial time approximation scheme for and arbitrary . [Feldman-monemizadeh-Sohler-Woodruff’10], [HarPeled-Varadarajan’02] [Shyamalkumar-Varadarajan’07], [Deshpande-Varadarajan’07].
- and arbitrary : Ratio approximation. [Varadarajan-Venkatesan-Ye-Zhang’07].
- For : let . [Deshpande-Tulsiani-Vishnoi’11] show -approximation for any and -approximation for .

**Previous results: Hardness**

- : NP-hard [Brieden-Gritzman-Klee’00]; inapproximable within [Varadarajan-Venkatesan-Ye-Zhang’07].
- , -approximation is UGC hard (even for ). [Deshpande-Tulsiani-Vishnoi’11].

Note that is the -th moment of a Gaussian, i.e.,

Definition 2-Grothendieck problem.

Input: An matrix with diagonal entries .

Output: A vector with .

Objective: Maximize .

- : easy, largest singular value.
- , “usual” Grothendieck problem. Admits -approximation. [Nesetrov’98, Megretski’99, Charikar-Wirth’04,…]. NP-hard to approximate within . [Arora-Berger-Hazan-Kindler-Safra’05].
- : [Kindler-Naor-Schechtman’08] proved -inapproximability assuming UGC conjecture, and a nearly matching algorithm.

**This talk**: NP-hard to achieve an approximation , as well as a approximation algorithm (also in [Naro-Schechtman], unpublished).

**2. Proofs **

Use reduction from LABEL COVER (aka MAX PROJECTION).

** 2.1. The gadget **

The gadget is a dictatorship test. Remember one wants to find a unit vector minimizing

Consider . If for , we see . If for some small , then . In order to see this, note that converges in law to a standard Gaussian by Central Limit Theorem, for a random element . A quantitative bound is

It follows that

Thus there is a -gap between dictators and functions with low influences on .

** 2.2. Reference hardness result **

We want to plug this gadget into -smooth to expanding MAX PROJECTION. Precisely, consider such that

- with for all . (-to-)
- For all , , we have . (-smoothness)
- For all and , we have . (expansion)

Theorem 3There exists such that -approximation for -to- and -smooth expanding MAX PROJECTION is NP-hard for all .

This is PCP + Parallel Repetition + a trick due to Khot. The key assumptions are that and soundness tends to zero. Expansion comes for free.

** 2.3. Plugging in the gadget **

Let . For , let

Write . Consider

If the value is less than , there exists about -fraction of such that has a coordinate with .

Would like

for all , . For any edge and element , define the vector as follows,

Take and let . Now

subject to and .

** 2.4. Analysis **

Completeness: Take . It has value since it is a dictator in each vertex.

Soundness: List-decode small sets of labels for fraction of vertices. Argue some sort of consistency.

Definition: Say is -irregular if

Let be the fraction of -irregular vertices. We already know that if is -regular,

So for , there exists such that -fractions of vertices are -irregular. So we need only worry on such vertices. For such a vertex , define

By construction, it is non empty and of size . We prove that for edges , and intersect. By -smoothness, the probability that this occurs is small.

**3. Comments **

Naor: Is the -subspace problem a special case of the Grothendieck problem ? Answer: essentially yes.

** References **

[GRSW] Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Ji; *Bypassing UGC from some optimal geometric inapproximability results.* ECCC Technical Report TR10-177