Undergrad Complexity at CMU - Hardness within P
Offered By: Ryan O'Donnell via YouTube
Course Description
Overview
Explore the intricacies of computational complexity theory in this undergraduate lecture from Carnegie Mellon University's Course 15-455. Delve into the concept of hardness within P, focusing on topics such as the Time Hierarchy Theorem, Strong Exponential Time Hypothesis, and fine-grained complexity. Learn about important problems like all-pairs shortest paths, k-clique, and context-free grammar parsing. Examine reduction techniques, including contrapositive and reduction algorithms, and discover new hardness results. Note a correction regarding the reduction from CNF-SAT to DIAMETER, where the truth assignment vertices need specific connections to special nodes. Engage with open questions in the field and gain insights from Professor Ryan O'Donnell's expertise in this comprehensive 82-minute session from Spring 2017.
Syllabus
Introduction
Time Hierarchy Theorem
Strong Exponential Time Hypothesis
All pairs shortest paths
K clique problem
Contextfree grammar parsing
New hardness results
Finegrained complexity
Reductions
Contrapositive
Reduction algorithms
Open Question
Taught by
Ryan O'Donnell
Related Courses
理论计算机科学基础 | Introduction to Theoretical Computer SciencePeking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam