Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee +1

Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results fo…