[metric 2011] Venkatesan Guruswami

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 21, 9:00-10:00
Venkatesan Guruswami (Carnegie Mellon U.)
Bypassing UGC: Inapproximability of Subspace Approximation
-------
The Unique Games conjecture (UGC) has emerged in recent years as the starting point for optimal inapproximability results for several problems. However, these problems are only known to be Unique-Games-hard but not Unique-Games-"complete", leaving open the possibility that while many of the implications of the UGC are true, the conjecture itself is false. The question of whether inapproximability results shown under the UGC can be shown without appealing to the conjecture is thus a well-motivated one. In this work, we bypass the UGC assumption in inapproximability results for two geometric problems --- subspace approximation and Grothendieck problems in \ell_p-norms --- obtaining a tight NP-hardness result in each case.

Joint work with Prasad Raghavendra, Rishi Saket, and Yi Wu.