Talk By Tal Herman
summary
Protocol shows how to verifiably obtain a tagged sample of size roughly √N using about √N samples and √N verifier time by interacting with a prover that supplies claimed probabilities. Verifier mixes D-samples with uniform samples (bits kept secret) and runs two checks: a consistency test (counts from D versus uniform) and an average-mass test (empirical second-moment/collision estimate), with bucketing to handle near values and a multiplicative average-error soundness measure. Open points: lower bounds, communication tradeoffs and further applications.
AI-written summary · about