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
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube