Seminars

View all Seminars  |  Download ICal for this event

Inapproximability of Sparsest Vector in a Real Subspace

Series: Bangalore Theory Seminars

Speaker: Vijay Bhattiprolu, University of Waterloo

Date/Time: Nov 04 16:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

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.

This talk is based on a joint work with David Rasmussen Lolck and Laura Mančinska.

Microsoft teams link:

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar