YoVDO

More on Constant-Round Interactive Proof Systems - Graduate Complexity Lecture at CMU

Offered By: Ryan O'Donnell via YouTube

Tags

Interactive Proof Systems Courses Polynomials Courses Computational Complexity Theory Courses

Course Description

Overview

Explore constant-round interactive proof systems in this graduate-level computational complexity theory lecture from Carnegie Mellon University. Delve into topics such as MA and AM, BPP, characterization of AM, interactive proofs, Merlin-Arthur proofs, private coins, efficient error reduction, and parallel repetition. Learn about polynomials, Arthur's coins and messages, Martha's final message, MA AM, and MA L. Examine concepts like Arthur-Merlin, fishing, sketching, fare reduction, amplification, and AMA. Gain insights into translation and compression within the context of interactive proof systems. This lecture, part of CMU's Course 15-855 in Fall 2017, is taught by Ryan O'Donnell and includes suggested readings from Arora-Barak Chapters 8.2.1 and 8.2.2.

Syllabus

Introduction
MA and AM
BPPV
Last time
Characterization of AM
Interactive proofs
Merlin Arthur proofs
Private coins
Efficient error reduction
Parallel repetition
Polynomials
Arthurs Coins
Arthurs Message
Arthurs Final Message
Marthas Final Message
MA AM
MA L
Arthur
Merlin
Fishin
Sketch
Fare reduction
Amplification
AMA
Any questions
Translation
Compression


Taught by

Ryan O'Donnell

Related Courses

Intermediate Algebra
University of California, Irvine via Coursera
Visualizing Algebra
San Jose State University via Udacity
College Algebra
San Jose State University via Udacity
Комбинаторика для начинающих
Moscow Institute of Physics and Technology via Coursera
Álgebra básica
Universidad Nacional Autónoma de México via Coursera