0

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

September 9, 2022

Duration:

EXPIRED

FREE

This course includes:

EXPIRED

Badge on Completion

Certificate of completion

EXPIRED

Description

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can’t be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP).

The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

Course Curriculum

  • Overview Unlimited
  • 3 Partition 1 Unlimited
  • 3 Partiotion 2 Unlimited
  • SAT 1 Unlimited
  • SAT Reductions Unlimited
  • Circuit SAT Unlimited
  • Planar SAT Unlimited
  • Hamiltonicity Unlimited
  • Graph Problems Unlimited
  • Inapproximabililty Overview Unlimited
  • Inapproximability Examples Unlimited
  • Gaps and PCP Unlimited
  • W Hierarchy Unlimited
  • ETH and Planar FPT Unlimited
  • #P and ASP Unlimited
  • NP and PSPACE Video Games Unlimited
  • Nondeterministic Constraint Logic Unlimited
  • 0 and 2 Player Games Unlimited
  • Unbounded Games Unlimited
  • Undecidable and p-Complete Unlimited
  • 3SUM And APSP Hardness Unlimited
  • PPAD Unlimited
  • PPAD Reduction Unlimited

About the instructor

5 5

Instructor Rating

1

Reviews

1520

Courses

1915

Students

Profile Photo
Massachusetts Institute of Technology