Title: Inapproximability of Sparsest Vector in a Real Subspace
| Speaker: | Vijay Bhattiprolu |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract:We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace (where sparsity refers to the number of nonzero entries). Formally we show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor. We recover as a corollary state of the art inapproximability factors for the shortest vector problem (SVP), a foundational problem in lattice based cryptography. Our proof is surprisingly simple, bypassing even the PCP theorem.
Our main motivation in this work is the development of inapproximability techniques for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which cause similar barriers to inapproximability. The approach we develop could lead to progress on the hardness of some of these problems.
Joint work with Euiwoong Lee.