Explore the SETH hardness of coding problems in this 22-minute IEEE conference talk presented by Noah Stephens-Davidowitz and Vinod Vaikuntanathan. Delve into linear codes, the Nearest Codeword Problem (NCP), and the Strong Exponential Time Hypothesis (SETH). Examine the reduction to NCP, 2-SAT without negations, and the process of finishing the reduction. Learn about negated variables and additional NCP results. Investigate the Minimum Distance Problem (MDP) and gain a comprehensive understanding of the topic through a concise summary.
Overview
Syllabus
SETH-Hardness of Coding Problems
Linear Codes
Nearest Codeword Problem (NCP)
The Strong Exponential Time Hypothesis (SETH)
Reduction to NCP
2-SAT without Negations...
Finishing the Reduction (without negations...)
Negated Variables
Additional NCP Results
Minimum Distance Problem (MDP)
Summary
Taught by
IEEE FOCS: Foundations of Computer Science
