Alladi Ramakrishnan Hall

Simple PCP-free Inapproximability of Minimum Distance and Nearest Codeword

Venkat Guruswami

U C Berkeley and Simons Institute, USA

The *minimum distance* problem (MDP) consists of finding the sparsest nonzero vector in a subspace over a finite field. We describe a reduction from the canonical NP-hard problem of solving systems of quadratic equations to the approximate version of MDP and to the related *nearest codeword problem* (the affine analog of MDP). Our reduction and proof are simple and PCP-free, based on the tensor product of a linear code whose codewords all have approximately the same weight. We hope to present the full proof in the talk. Time permitting, we will also mention analogous results for the Shortest Vector Problem on lattices.

Based on joint work with Vijay Bhattiprolu, Euiwoong Lee, and Xuandi Ren.