Valiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMU

Item: Valiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMU
Rating: 5
Author: PostSingularity Institute

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYAMathematical theory of computation

🎙 Ryan O'Donnell 👥 14K 📅 October 21, 2017 ⏱ 76 min 👁 1K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

Valiant-VaziraniUnique-SAT#PExact CountingRandomized Reduction

Summary

This graduate lecture at CMU, taught by Ryan O’Donnell, covers two main topics: the Valiant-Vazirani theorem and the complexity class #P. The lecture begins by reviewing the approximate counting problem and its connection to the class AM. It then introduces the Unique-SAT problem, where a circuit is promised to have either zero or one satisfying assignment. The Valiant-Vazirani theorem states that Unique-SAT is not easier than general SAT under randomized reductions. The proof uses pairwise-independent hash functions to reduce the number of satisfying assignments to one with high probability. The lecture then defines the class #P, which consists of functions counting the number of accepting paths of a nondeterministic polynomial-time Turing machine. Several examples of #P problems are given, including #Circuit-SAT, #DNF-SAT, and counting perfect matchings in bipartite graphs. The lecture emphasizes that counting versions of easy decision problems can be very hard, and that #P is believed to be significantly harder than NP.

154 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and detailed proof of the Valiant-Vazirani theorem, explaining the use of hash functions and the probabilistic analysis. It also offers a clear definition of #P and illustrates it with several examples, highlighting the contrast between easy decision problems and hard counting problems. The argumentation is solid, building on previous lectures and standard textbook material.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the Arora-Barak textbook, specifically chapters 17.0, 17.1, 17.2.1, 17.3.2, and 17.4.1. The instructor is a well-known researcher in computational complexity, and the content is presented with mathematical precision. The title accurately reflects the content, covering both the Valiant-Vazirani theorem and the #P class. No comments were provided for analysis.

128 words

Title / Content Match

The title accurately reflects the content, covering the Valiant-Vazirani theorem and the #P class.

Quality & Reliability

9/10

Lecture by a renowned professor at CMU, based on standard textbook (Arora-Barak), with rigorous proofs and clear explanations.

Key Moments

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

Cited Sources

Ryan O'Donnell's homepage — Instructor's homepage
Course website for 15-855 — Course materials and suggested reading
Panopto — Video recording platform

Concurring Sources

Arora-Barak textbook — Suggested reading for the lecture, covering related topics in detail.

Contribution & Novelties

The lecture provides a clear and rigorous exposition of the Valiant-Vazirani theorem and the #P class, with detailed proofs and examples. It emphasizes the surprising hardness of counting problems even when decision is easy.

Pour aller plus loin :

Valiant-Vazirani theorem — Overview of the theorem and its implications.
#P complexity class — Definition and key results.
Arora-Barak textbook — Standard reference for computational complexity, including chapters on counting.

69 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