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 sho...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130061 |
| _version_ | 1811071343241723904 |
|---|---|
| author | Stephens-Davidowitz, Noah Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Stephens-Davidowitz, Noah Vaikuntanathan, Vinod |
| author_sort | Stephens-Davidowitz, Noah |
| collection | MIT |
| description | 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, or NCPP algorithms running in time q (1-ϵ)n for any constant ϵ>0 for codes with qn codewords. (In the case of NCPP, we assume non-uniform SETH.) We also show that there are no sub-exponential time algorithms for γ-Approximate versions of these problems for some constant γ > 1, under different versions of the exponential-Time hypothesis. |
| first_indexed | 2024-09-23T08:49:40Z |
| format | Article |
| id | mit-1721.1/130061 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:49:40Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1300612024-06-25T17:48:28Z SETH-Hardness of Coding Problems Stephens-Davidowitz, Noah Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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, or NCPP algorithms running in time q (1-ϵ)n for any constant ϵ>0 for codes with qn codewords. (In the case of NCPP, we assume non-uniform SETH.) We also show that there are no sub-exponential time algorithms for γ-Approximate versions of these problems for some constant γ > 1, under different versions of the exponential-Time hypothesis. NSF-BSF (Grant 1718161) NSF (Award 1350619) 2021-03-03T15:15:20Z 2021-03-03T15:15:20Z 2020-01 2019-11 2021-02-25T13:47:32Z Article http://purl.org/eprint/type/ConferencePaper 9781728149523 9781728149530 2575-8454 https://hdl.handle.net/1721.1/130061 Stephens-Davidowitz, Noah and Vinod Vaikuntanathan. "SETH-Hardness of Coding Problems." 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, November 2019, Baltimore, Maryland, Institute of Electrical and Electronics Engineers, January 2020. © 2019 IEEE en http://dx.doi.org/10.1109/focs.2019.00027 2019 IEEE 60th Annual Symposium on Foundations of Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Vinod Vaikuntanathan via Phoebe Ayers |
| spellingShingle | Stephens-Davidowitz, Noah Vaikuntanathan, Vinod SETH-Hardness of Coding Problems |
| title | SETH-Hardness of Coding Problems |
| title_full | SETH-Hardness of Coding Problems |
| title_fullStr | SETH-Hardness of Coding Problems |
| title_full_unstemmed | SETH-Hardness of Coding Problems |
| title_short | SETH-Hardness of Coding Problems |
| title_sort | seth hardness of coding problems |
| url | https://hdl.handle.net/1721.1/130061 |
| work_keys_str_mv | AT stephensdavidowitznoah sethhardnessofcodingproblems AT vaikuntanathanvinod sethhardnessofcodingproblems |