Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Hardness of Coding Problems

IEEE via YouTube

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

Reviews

Start your review of Hardness of Coding Problems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.