YoVDO

Crash Course on Probabilistically Checkable Proofs - Introduction

Offered By: Simons Institute via YouTube

Tags

Probabilistically Checkable Proofs Courses Geometry Courses Probability Courses Approximation Algorithms Courses

Course Description

Overview

Explore the fundamental concepts of Probabilistically Checkable Proofs (PCP) in this comprehensive lecture by Irit Dinur from the Weizmann Institute. Delve into topics such as recoloring, constraint satisfaction, and the PCP Theorem. Gain insights into the dramatized perspective of proof pie, PCP verifier, and verifier parameters. Examine the hardness of approximation and approximation algorithms. Presented as part of the Probability, Geometry, and Computation in High Dimensions Boot Camp at the Simons Institute, this hour-long talk provides a crash course on PCP, offering a solid foundation for further study in computational complexity theory.

Syllabus

Introduction
What is Recoloring
Constraint Satisfaction
PCP Theorem
Questions
dramatized perspective
Proof Pie
PCP Verifier
Verifier Parameters
Hardness of approximation
approximation algorithms
Summary


Taught by

Simons Institute

Related Courses

Design of Computer Programs
Stanford University via Udacity
Intro to Statistics
Stanford University via Udacity
Health in Numbers: Quantitative Methods in Clinical & Public Health Research
Harvard University via edX
Mathematical Biostatistics Boot Camp 1
Johns Hopkins University via Coursera
Statistics
San Jose State University via Udacity