Hardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory Toolkit

Hardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 July 16, 2020 ⏱ 23 min 👁 809 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

3XOR3SathardnessFeige's Hypothesisrandom CSP

Summary

This lecture, part of a graduate course on CS theory, discusses the hardness of random 3XOR and 3Sat problems. It begins with the sparse learning parity with noise (LPN) problem, where each equation involves only a constant number of variables, and explains why it is believed to be hard. The lecture then transitions to the worst-case NP-hardness of approximating 3XOR, citing Håstad’s theorem, and outlines the long reduction chain from 3SAT via the PCP theorem and parallel repetition. It highlights how sparse LPN can generate random hard instances that can be fed into reductions to produce hard instances of other problems like TSP and graph isomorphism. The second half focuses on random 3Sat, discussing the sharp threshold for satisfiability and the difficulty of certifying unsatisfiability. It introduces Feige’s 3Sat hypothesis, which posits that no polynomial-time algorithm can find certificates of unsatisfiability for random 3Sat instances with a sufficiently large constant clause density. The lecture concludes by noting the connections between these hypotheses and their implications for hardness of learning.

169 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides valuable insights into the hardness of random constraint satisfaction problems, bridging worst-case and average-case complexity. The argumentation is solid, building from the sparse LPN problem to Håstad’s theorem and Feige’s hypothesis, with clear explanations of why these problems are believed to be hard. The lecturer effectively uses examples and intuitive reasoning to support the claims, making the material accessible while maintaining rigor.

Scientific Rigor, Source Quality, Title Accuracy

The lecture demonstrates high scientific rigor, referencing key theorems and hypotheses such as Håstad’s 3XOR hardness, the PCP theorem, and Feige’s 3Sat hypothesis. The sources are authoritative, and the title accurately reflects the content. The lecture is part of a well-structured course, and the lecturer’s expertise adds to its credibility.

130 words

Title / Content Match

The title accurately reflects the content, which covers hardness of random 3XOR and 3Sat problems.

Quality & Reliability

9/10

Lecture by a renowned professor in theoretical computer science, presenting established results and open hypotheses with clear explanations. The content is rigorous and well-structured, though it is a lecture rather than peer-reviewed material.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

  • Håstad's 3XOR hardness — Confirms the NP-hardness of approximating 3XOR.
  • PCP theorem — Confirms the role of PCP theorem in hardness of approximation.

Contribution & Novelties

The lecture provides a clear and accessible overview of the hardness of random 3XOR and 3Sat problems, connecting worst-case and average-case complexity. It emphasizes the practical use of sparse LPN to generate hard instances and introduces Feige’s hypothesis as a powerful assumption for proving hardness of learning.

Pour aller plus loin :

  • Håstad’s 3XOR hardness — Key theorem on NP-hardness of approximating 3XOR.
  • PCP theorem — Foundational result in hardness of approximation.
  • Feige’s 3Sat hypothesis — Assumption about hardness of random 3Sat.
  • Learning parity with noise — Related problem in learning theory.

92 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous, with strong reliability and depth.

Reliability 9/10