Hardness of Coding Problems
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
Approximation Algorithms Part IÉcole normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Automata Theory
Stanford University via edX Computation in Complex Systems
Santa Fe Institute via Complexity Explorer Computing: Art, Magic, Science
ETH Zurich via edX