1 of 48

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

2 of 48

Agenda

  • Goal: To give a full proof of a PCP theorem (mod details ☺)
    • Omitted Details: Analysis
    • Included Details:
      • Full description of PCP verifier
      • Honest Prover
      • Including Pseudocode (small fonts)

​

Boston Complexity Day: Simple PCP

2

October 23, 2026

of 35

3 of 48

PCP Theorem

  •  

Boston Complexity Day: Simple PCP

3

October 23, 2026

of 35

4 of 48

History

  • First proof: [Arora-Safra, Arora-Lund-Motwani-S.-Szegedy ‘92]
  • Alternate proof: [Dinur ‘06]
  • Before/after: Many extensions/strengthenings … mostly complexifications.
    • Includes [Raz’94, Hastad ‘97, BenSasson-Goldreich-Harsha-S.-Vadhan ‘04, BenSasson-S ‘05, Moshkovitz-Raz ’07] …
  • This talk: A simple algebraic proof (so simplifies ALMSS’92)
    • Comparison with Dinur? (not comparable? Similar? Slightly more complex?)

Boston Complexity Day: Simple PCP

4

October 23, 2026

of 35

5 of 48

History

  • First proof: [Arora-Safra, Arora-Lund-Motwani-S.-Szegedy ‘92]
  • Alternate proof: [Dinur ‘06]
  • Before/after: Many extensions/strengthenings … mostly complexifications.
    • Includes [Raz’94, Hastad ‘97, BenSasson-Goldreich-Harsha-S.-Vadhan ‘04, BenSasson-S ‘05, Moshkovitz-Raz ’07] …
  • This talk: A simple algebraic proof (so simplifies ALMSS’92)
    • Comparison with Dinur? (not comparable? Similar? Slightly more complex?)
  • Some virtues:
    • Verifier has “low” Kolmogorov Complexity
    • Completeness Prover has “low” Kolmogorov Complexity

Boston Complexity Day: Simple PCP

5

October 23, 2026

of 35

6 of 48

Verifier and Completeness Prover

Boston Complexity Day: Simple PCP

6

October 23, 2026

of 35

7 of 48

Rest of the talk

  •  

Boston Complexity Day: Simple PCP

7

October 23, 2026

of 35

8 of 48

Rest of the talk

  •  

Boston Complexity Day: Simple PCP

8

October 23, 2026

of 35

9 of 48

I. A Basic PCP

Boston Complexity Day: Simple PCP

9

October 23, 2026

of 35

10 of 48

Notations/Conventions

  •  

Boston Complexity Day: Simple PCP

10

October 23, 2026

of 35

11 of 48

3-coloring and arithmetization

  •  

Boston Complexity Day: Simple PCP

11

October 23, 2026

of 35

12 of 48

3-coloring and arithmetization

  •  

Boston Complexity Day: Simple PCP

12

October 23, 2026

of 35

13 of 48

3-coloring and arithmetization

  •  

Boston Complexity Day: Simple PCP

13

October 23, 2026

of 35

14 of 48

Arithmetizing correctly

  •  

Boston Complexity Day: Simple PCP

14

October 23, 2026

of 35

15 of 48

Arithmetizing correctly

  •  

Boston Complexity Day: Simple PCP

15

October 23, 2026

of 35

16 of 48

3-coloring and arithmetization

  •  

Boston Complexity Day: Simple PCP

16

October 23, 2026

of 35

17 of 48

Towards a PCP

  •  

Boston Complexity Day: Simple PCP

17

October 23, 2026

of 35

18 of 48

Low-degree Testing

  •  

Boston Complexity Day: Simple PCP

18

October 23, 2026

of 35

19 of 48

Low-degree testing (contd.)

  •  

Boston Complexity Day: Simple PCP

19

October 23, 2026

of 35

20 of 48

Zero-on-V testing

  •  

Boston Complexity Day: Simple PCP

20

October 23, 2026

of 35

21 of 48

Zero-on-V testing

  •  

Boston Complexity Day: Simple PCP

21

October 23, 2026

of 35

22 of 48

Zero-on-V testing

  •  

Boston Complexity Day: Simple PCP

22

October 23, 2026

of 35

23 of 48

 

  •  

Boston Complexity Day: Simple PCP

23

October 23, 2026

of 35

24 of 48

 

  •  

Boston Complexity Day: Simple PCP

24

October 23, 2026

of 35

25 of 48

 

  •  

Boston Complexity Day: Simple PCP

25

October 23, 2026

of 35

26 of 48

A (very weak) PCP Theorem

  •  

Boston Complexity Day: Simple PCP

26

October 23, 2026

of 35

27 of 48

 

Boston Complexity Day: Simple PCP

27

October 23, 2026

of 35

28 of 48

 

  •  

Boston Complexity Day: Simple PCP

28

October 23, 2026

of 35

29 of 48

 

  •  

Boston Complexity Day: Simple PCP

29

October 23, 2026

of 35

30 of 48

The actual ALMSS Path

Boston Complexity Day: Simple PCP

30

October 23, 2026

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

of 35

31 of 48

 

  •  

Boston Complexity Day: Simple PCP

31

October 23, 2026

of 35

32 of 48

 

  •  

Boston Complexity Day: Simple PCP

32

October 23, 2026

of 35

33 of 48

The updated ALMSS Path

Boston Complexity Day: Simple PCP

33

October 23, 2026

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

X

X

of 35

34 of 48

III. PCP with one composition

Boston Complexity Day: Simple PCP

34

October 23, 2026

of 35

35 of 48

2. Generalized Zero-on-V(ariety) tests

  •  

Boston Complexity Day: Simple PCP

35

October 23, 2026

of 35

36 of 48

Macaulay Complexity & PCPs

  •  

Boston Complexity Day: Simple PCP

36

October 23, 2026

of 35

37 of 48

Useful Varieties

  •  

Boston Complexity Day: Simple PCP

37

October 23, 2026

of 35

38 of 48

Useful Varieties

  •  

Boston Complexity Day: Simple PCP

38

October 23, 2026

of 35

39 of 48

PCP Theorem w. 1 composition

Boston Complexity Day: Simple PCP

39

October 23, 2026

  •  
  •  
  •  
  •  

of 35

40 of 48

IV. PCP with zero (half?) composition

Boston Complexity Day: Simple PCP

40

October 23, 2026

of 35

41 of 48

PCP with 0 compositions?

  •  

Boston Complexity Day: Simple PCP

41

October 23, 2026

of 35

42 of 48

PCP with 0 compositions?

  •  

Boston Complexity Day: Simple PCP

42

October 23, 2026

of 35

43 of 48

Encoding for low-degree testing:

  •  

Boston Complexity Day: Simple PCP

43

October 23, 2026

of 35

44 of 48

 

Boston Complexity Day: Simple PCP

44

October 23, 2026

  •  

of 35

45 of 48

 

Boston Complexity Day: Simple PCP

45

October 23, 2026

  •  

of 35

46 of 48

Verifier and Completeness Prover

Boston Complexity Day: Simple PCP

46

October 23, 2026

of 35

47 of 48

Verifier and Completeness Prover

Boston Complexity Day: Simple PCP

47

October 23, 2026

  • Lean formalization!
  • Kudos to Troy Lee!
  • See also: Github code
  • (written by Sophus

and Claude)

  • ~500 lines of Python
  • includes all algebra

and comments!

  • Uses only math and

itertools packages

  • First PCP[log n, O(1)]

implementation?

of 35

48 of 48

Thank you!

Boston Complexity Day: Simple PCP

48

October 23, 2026

of 35