YoVDO

Undergrad Complexity at CMU - Hardness within P

Offered By: Ryan O'Donnell via YouTube

Tags

Computational Complexity Theory Courses Fine-Grained Complexity Courses

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 Science
Peking 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