The Unique Games Conjecture (UGC) asserts that a certain two variable constraint satisfaction problem with bijective constraints is NP-hard to approximate. While the conjecture remains an important open question, it has yielded several optimal inapproximability results - many of which depend critically on the assumption of bijective constraints. In this talk we shall observe that some geometric inapproximability results - previously only known based on the UGC - can be shown without appealing to the conjecture.

Specifically, I shall present optimal NP-hardness of approximation results obtained in recent work [GRSW 11] for two problems: the L_p Subspace Approximation Problem and the L_p Quadratic Grothendieck Maximization Problem for constant p > 2. These results are based onthe so called "smooth" Label Cover instances which have "locally bijective" constraints. Such instances have also been used in earlier work [KS 08] to prove optimal hardness of learning intersections of two halfspaces. The focus of the talk would be to illustrate how assumption of the UGC can be avoided in proving the mentioned results.