Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > VINOD VAIKUNTANATHAN:
All reports by Author Vinod Vaikuntanathan:

TR19-159 | 11th November 2019
Noah Stephens-Davidowitz, Vinod Vaikuntanathan

SETH-hardness of Coding Problems

We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, ... more >>>




ISSN 1433-8092 | Imprint