Boston Complexity Day: Simple PCP
1
October 23, 2026
Simple(r) Algebraic PCPs
Based on
Madhu Sudan
Harvard
Joint work with: Prashanth Amireddy (Harvard), Amik Raj Behera,
Srikanth Srinivasan, Sophus Valentin Willumsgaard (U. Copehagen)
of 35
Agenda
Boston Complexity Day: Simple PCP
2
October 23, 2026
of 35
PCP Theorem
Boston Complexity Day: Simple PCP
3
October 23, 2026
of 35
History
Boston Complexity Day: Simple PCP
4
October 23, 2026
of 35
History
Boston Complexity Day: Simple PCP
5
October 23, 2026
of 35
Verifier and Completeness Prover
Boston Complexity Day: Simple PCP
6
October 23, 2026
of 35
Rest of the talk
Boston Complexity Day: Simple PCP
7
October 23, 2026
of 35
Rest of the talk
Boston Complexity Day: Simple PCP
8
October 23, 2026
of 35
I. A Basic PCP
Boston Complexity Day: Simple PCP
9
October 23, 2026
of 35
Notations/Conventions
Boston Complexity Day: Simple PCP
10
October 23, 2026
of 35
3-coloring and arithmetization
Boston Complexity Day: Simple PCP
11
October 23, 2026
of 35
3-coloring and arithmetization
Boston Complexity Day: Simple PCP
12
October 23, 2026
of 35
3-coloring and arithmetization
Boston Complexity Day: Simple PCP
13
October 23, 2026
of 35
Arithmetizing correctly
Boston Complexity Day: Simple PCP
14
October 23, 2026
of 35
Arithmetizing correctly
Boston Complexity Day: Simple PCP
15
October 23, 2026
of 35
3-coloring and arithmetization
Boston Complexity Day: Simple PCP
16
October 23, 2026
of 35
Towards a PCP
Boston Complexity Day: Simple PCP
17
October 23, 2026
of 35
Low-degree Testing
Boston Complexity Day: Simple PCP
18
October 23, 2026
of 35
Low-degree testing (contd.)
Boston Complexity Day: Simple PCP
19
October 23, 2026
of 35
Zero-on-V testing
Boston Complexity Day: Simple PCP
20
October 23, 2026
of 35
Zero-on-V testing
Boston Complexity Day: Simple PCP
21
October 23, 2026
of 35
Zero-on-V testing
Boston Complexity Day: Simple PCP
22
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
23
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
24
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
25
October 23, 2026
of 35
A (very weak) PCP Theorem
Boston Complexity Day: Simple PCP
26
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
27
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
28
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
29
October 23, 2026
of 35
The actual ALMSS Path
Boston Complexity Day: Simple PCP
30
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
31
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
32
October 23, 2026
of 35
The updated ALMSS Path
Boston Complexity Day: Simple PCP
33
October 23, 2026
X
X
of 35
III. PCP with one composition
Boston Complexity Day: Simple PCP
34
October 23, 2026
of 35
2. Generalized Zero-on-V(ariety) tests
Boston Complexity Day: Simple PCP
35
October 23, 2026
of 35
Macaulay Complexity & PCPs
Boston Complexity Day: Simple PCP
36
October 23, 2026
of 35
Useful Varieties
Boston Complexity Day: Simple PCP
37
October 23, 2026
of 35
Useful Varieties
Boston Complexity Day: Simple PCP
38
October 23, 2026
of 35
PCP Theorem w. 1 composition
Boston Complexity Day: Simple PCP
39
October 23, 2026
of 35
IV. PCP with zero (half?) composition
Boston Complexity Day: Simple PCP
40
October 23, 2026
of 35
PCP with 0 compositions?
Boston Complexity Day: Simple PCP
41
October 23, 2026
of 35
PCP with 0 compositions?
Boston Complexity Day: Simple PCP
42
October 23, 2026
of 35
Encoding for low-degree testing:
Boston Complexity Day: Simple PCP
43
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
44
October 23, 2026
of 35
Boston Complexity Day: Simple PCP
45
October 23, 2026
of 35
Verifier and Completeness Prover
Boston Complexity Day: Simple PCP
46
October 23, 2026
of 35
Verifier and Completeness Prover
Boston Complexity Day: Simple PCP
47
October 23, 2026
and Claude)
and comments!
itertools packages
implementation?
of 35
Thank you!
Boston Complexity Day: Simple PCP
48
October 23, 2026
of 35