Erasures vs. Errors in Local Decoding and Property Testing
summary
Constructs a specific n-bit property that is alpha-erasure-resilient testable with constant queries yet requires polynomial (indeed near-linear) queries for tolerant/error-resilient testing. Proof uses PCPs of proximity plus an encoding that concatenates repeated plain copies of x with a locally list-decodable code of x||π (used Hadamard as the concrete code), and a tester that runs the local list-decoder and the PCP verifier on O(1) decoded bits. Result: constant vs. poly(n) separation holds; stronger separations hinge on existence of better locally list-decodable codes.
AI-written summary · about
chapters (13)
- 0:00Intro
- 5:13Property Testing with Errors
- 6:24Relationships Between Models
- 10:14Main Tool: Locally List Erasure-Decodeable Codes
- 14:32Hadamard Code
- 18:373CNF Properties: Hard to Test, Easy to Decide
- 20:12Testing with Advice: PCPs of Proximity (PCPP)
- 21:50Testing 3CNF Properties with/without a Proof
- 24:33Separating Property: Erasure-Resilient Testing
- 28:32Separating Property: Hardness of Tolerunt Testing
- 34:16Strengthening the Separation: Challenges
- 35:44Strengthening the Separation: Main Ideas
- 38:34Open Questions and Directions
related talks
44mStochastic Integration via Error-Correcting Codes
30mUnfamiliar Terrain
37mEfficient Algorithms for Reliable Machine Learning
19mCounterexamples to the Low-Degree Conjecture
31mStatistical Estimation on Graphs
43mIs Interaction Necessary for Distributed Private Learning?
45mTeaching an old code a new trick
01h 00mAverage-case Complexity for Polynomials, and All That