Algebraic Circuit Complexity: Graduate Complexity Lecture 15 at CMU

Item: Algebraic Circuit Complexity: Graduate Complexity Lecture 15 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 📅 November 5, 2017 ⏱ 80 min 👁 2K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

algebraic circuitarithmetic circuitcomplexity classesVPVNPpermanentdeterminantValiant's theoremHorner's methodfast Fourier transform

Summary

This is the fifteenth lecture in a graduate computational complexity course at Carnegie Mellon University, taught by Ryan O’Donnell. The lecture introduces algebraic complexity theory, focusing on algebraic circuits and the complexity of computing polynomials. It begins with motivating problems such as polynomial evaluation (Horner’s method), polynomial multiplication (using FFT), and matrix multiplication (Strassen’s algorithm). The basic model of algebraic circuits is defined, including gates for addition, multiplication, and scalar multiplication, with inputs as variables and scalars from a field (typically complex numbers). Two cost models are discussed: total cost and non-scalar cost. Simple examples illustrate the complexity of computing products and powers, highlighting the role of division and the difference between circuits and formulas. The lecture then introduces p-families (polynomials of polynomially bounded degree) and the complexity classes VP and VNP, which are algebraic analogs of P and NP. The permanent is shown to be VNP-complete (Valiant’s theorem), while the determinant is in VP. The lecture concludes with a discussion of the determinant vs. permanent problem and its implications for algebraic complexity theory.

174 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a comprehensive and insightful introduction to algebraic complexity theory. It effectively motivates the subject with classical problems and presents the key definitions and results with clarity. The argumentation is rigorous, building from simple examples to the definition of complexity classes and the statement of Valiant’s theorem. The lecturer’s expertise is evident in the careful explanations and the connections drawn between algebraic and boolean complexity. The value lies in its ability to convey the fundamental concepts and open problems of the field in a single lecture, making it an excellent resource for graduate students and researchers.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, based on established research in algebraic complexity theory. The lecturer references the standard textbook by Arora and Barak (Chapter 16.1) and mentions key results and researchers (e.g., Ostrowski, Karatsuba, Strassen, Cooley-Tukey, Valiant). The sources are appropriate for a graduate-level course. The title accurately reflects the content, as it is indeed a lecture on algebraic circuit complexity. The lecture is well-structured and the technical content is presented with precision.

186 words

Title / Content Match

The title accurately reflects the content: a graduate-level lecture on algebraic circuit complexity.

Quality & Reliability

9/10

Lecture by a recognized expert in computational complexity, part of a graduate course at CMU. Content is rigorous, well-structured, and based on established research. The lecture is a formal academic presentation, not popularized content.

Key Moments

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

Cited Sources

Ryan O'Donnell's homepage — Lecturer's academic page.
Course website for 15-855 — Course materials and syllabus.
Panopto — Video recording platform.

Concurring Sources

Arora & Barak, Computational Complexity: A Modern Approach — Textbook referenced in the lecture for further reading.

Contribution & Novelties

This lecture provides a concise yet comprehensive overview of algebraic complexity theory, making it accessible to graduate students. It bridges classical results (Horner, FFT, Strassen) with modern complexity classes (VP, VNP) and highlights the central open problem of separating VP from VNP. The lecture’s novelty lies in its pedagogical approach, condensing a vast field into a single session while maintaining rigor.

Pour aller plus loin :

Valiant’s theorem on Wikipedia — Overview of the completeness of the permanent for VNP.
Arithmetic circuit complexity on Wikipedia — General introduction to the field.
Strassen algorithm on Wikipedia — Details on fast matrix multiplication.
Fast Fourier transform on Wikipedia — Explanation of the FFT algorithm.

112 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a well-balanced and rigorous lecture. The high technical level and information quality are consistent with a graduate course, while the strong reliability reflects the lecturer's expertise and the academic context.

Reliability 9/10

💬 No comments were provided for analysis.