Главная
Study mode:
on
1
Introduction
2
MA and AM
3
BPPV
4
Last time
5
Characterization of AM
6
Interactive proofs
7
Merlin Arthur proofs
8
Private coins
9
Efficient error reduction
10
Parallel repetition
11
Polynomials
12
Arthurs Coins
13
Arthurs Message
14
Arthurs Final Message
15
Marthas Final Message
16
MA AM
17
MA L
18
Arthur
19
Merlin
20
Fishin
21
Sketch
22
Fare reduction
23
Amplification
24
AMA
25
Any questions
26
Translation
27
Compression
Description:
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.

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

Ryan O'Donnell
Add to list
0:00 / 0:00