Topics in Theoretical Computer Science: Probabilistically Checkable Proofs

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Lecture Notes; Problem Sets
  • Before you start: MIT students need permission of instructor.
MIT OpenCourseWare details
  • As taught in: Fall 2022
  • Department: Mathematics
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Text Based

Specification
Access

Free Access

Academic Level

Graduate

SKU: topics-theoretical-computer-science-probabilistically Category: Tag: Brand:

The PCP theorem and hardness of approximation, including low-degree testing, long codes, parallel repetition and the Unique-Games Conjecture.

At a glance
LevelAll Levels
AccessFree access
FormatText Based
As taught inFall 2022
DepartmentMathematics
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

Some NP-hard problems stay NP-hard even when you only want an answer close to the optimum, and proving that requires the PCP theorem. This class presents the theory of probabilistically checkable proofs, starting with an algebraic proof of the basic theorem. It then moves to hardness amplification, the long-code framework, the Unique-Games Conjecture and the 2-to-2 Games Theorem.

What You Will Achieve

  • Follow the algebraic proof of the basic PCP Theorem
  • Use error correcting codes and low-degree testing in proof constructions
  • Derive hardness of approximation results for clique and set cover
  • Explain the Unique-Games Conjecture and its link to Max-cut


Program Overview

The Basic PCP Theorem

The first half builds the proof from coding and algebraic tools.

  • Error correcting codes
  • The sum-check protocol
  • Low-degree testing
  • Hadamard codes and composition

Hardness of Approximation

Next the theorem is applied, and repetition makes the results stronger.

  • Hardness of approximating the maximum clique
  • The Parallel Repetition Theorem
  • Reduction from label-cover to set-cover

Long Codes and Unique Games

The closing lectures reach optimal results and a major conjecture.

  • The long-code paradigm
  • Optimal inapproximability results
  • The Unique-Games Conjecture
  • Goemans-Williamson algorithm and Max-cut

Course Completion


Job Outlook

This theory serves research in theoretical computer science, particularly on approximation and complexity.


Our take

Good for: Theory students and researchers who want a full treatment of PCPs and hardness of approximation, with hard starred problems to test themselves.

Keep in mind: The materials are lecture notes and five problem sets, with no solutions listed and no videos.

Bottom line: A focused route through the PCP theorem and its consequences, closing on more recent advances.

Frequently Asked Questions

What are the starred problems?

The five problem sets mix problems of normal difficulty with more challenging ones marked with a star. Normal problems were enough for an A-, and higher grades needed a substantial number of starred ones.

Where can I find related material?

The syllabus names online courses by Subhash Khot at NYU, Irit Dinur and Dana Moshkovitz at the Weizmann Institute, and Alessandro Chiesa at Berkeley.

Does it cover recent results?

Yes. The description lists the 2-to-2 Games Theorem among the advanced topics, along with hardness amplification and the Unique-Games Conjecture and its implications.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
    Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0