Distributed Interactive Proofs
summary
Shows that MAM protocol verifies graph symmetry in O(log n) bits per node by having the prover commit a permutation and a rooted spanning tree, then nodes locally hash their neighborhood-rows and sum hashes up the tree with a linear hash to check the permuted adjacency matrix; AM gets O(n log n) and there is an easy Ω(log n) AM lower bound. Adapts Goldwasser–Sipser set-size hashing (using almost pairwise-independent hashes computable up a tree) for graph non-isomorphism; protocols are explicit and succeed with small proofs, leaving some AM lower-bound questions open.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:42DISTRIBUTED VERIFICATION
- 1:54PROOF LABELING SCHEMES KORMAN, KUTTEN '071
- 5:40EXAMPLE: CONNECTIVITY
- 7:32DISTRIBUTED AM
- 11:09GRAPH SYMMETRY
- 12:38MAM PROTOCOL FOR SYMMETRY
- 15:15THE PERMUTED ADJACENCY MATRIX
- 17:48HASHING THE ADJACENCY MATRIX
- 18:11THE PROTOCOL
- 20:46GOING DOWN TO AM
- 21:43LOWER BOUND FOR AM
- 22:42THE SETUP
- 26:27GOLDWASSER-SIPSER PROTOCOL
- 28:42DISTRIBUTED IMPLEMENTATION
- 29:37CONCLUSION
