Approximate Counting - Graduate Complexity Lecture at CMU

Offered By: Ryan O'Donnell via YouTube

Course Description

Overview

Explore the intricacies of approximate counting in this graduate-level lecture on Computational Complexity Theory. Delve into key concepts such as Chebyshev's Inequality, decision versions, interactive proofs, and the relationship between decision and approximation. Learn about the role of randomness in approximate counting algorithms. Part of Carnegie Mellon University's Course 15-855 for Fall 2017, this 80-minute lecture is taught by Professor Ryan O'Donnell and includes suggested readings from Arora-Barak Chapters 8.2.1 and 8.2.2.

Syllabus

Introduction
Chebyshevs Inequality
Approximate counting
Decision version
Interactive proof
Decision vs approximation
Randomness

Taught by

Ryan O'Donnell

Related Courses

理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam