31 episodes

This is an advanced class on algorithmic reduction, focusing on techniques for proving problems are complete with respect to various complexity classes.

Algorithmic Lower Bounds: Fun with Hardness Proof‪s‬ MIT

    • Technology

This is an advanced class on algorithmic reduction, focusing on techniques for proving problems are complete with respect to various complexity classes.

    • video
    Lecture 1: Overview

    Lecture 1: Overview

    In this lecture, Professor Demaine gives a brief overview of the class, summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games.

    • 1 hr 17 min
    • video
    Lecture 2: 3-Partition I

    Lecture 2: 3-Partition I

    In this lecture, Professor Demaine introduces the concept of 3-partition and its many variations, a starting point for NP-hardness reductions. Weak and strong NP-hardness proofs are seen in the context of other examples.

    • 1 hr 23 min
    • video
    Lecture 3: 3-Partition II

    Lecture 3: 3-Partition II

    In this lecture, Professor Demaine continues deriving strong NP-hardness reductions from 3-partition, and weak NP-hardness reductions from 2-partition.

    • 1 hr 20 min
    • video
    Lecture 4: SAT I

    Lecture 4: SAT I

    In this lecture, Professor Demaine starts a series of lectures on satisfiability, including using SAT to prove NP-hardness.

    • 1 hr 20 min
    • video
    Lecture 5: SAT Reductions

    Lecture 5: SAT Reductions

    In this lecture, Professor Demaine explains hardness proofs of games and puzzles, and graph theoretic problems, all reducing from 3-SAT.

    • 1 hr 21 min
    • video
    Lecture 6: Circuit SAT

    Lecture 6: Circuit SAT

    In this lecture, Professor Demaine explains the concept of circuit SAT.

    • 1 hr 18 min

Top Podcasts In Technology

Listeners Also Subscribed To

More by MIT