Verifiable Data Science via Interactive Proofs

on YouTube ↗01h 07m

" summary

Work describes concrete interactive‑proof systems that let a lightweight verifier check statistical claims using far fewer samples than re‑running the analysis: for label‑invariant distribution tasks there is a private‑coin two‑message protocol with verifier sample and communication complexity about √N (prover uses quasi‑linear samples/time), and that sample bound is information‑theoretically optimal; agnostic learning verification uses about √VC samples; for general properties decidable in bounded depth/space the construction yields tolerant proofs with verifier complexity roughly N^0.95 via reductions to interactive proofs of proximity plus a verified tagged samples primitive.

AI-written summary · about

" chapters (14)

1. 0:00Verifiable data science intro
2. 1:05Motivation for verifying analyses
3. 3:36Trusting data vs algorithms
4. 8:10Verifying with proof systems
5. 15:45Real-world proof applications
6. 16:06Verifying agnostic learning tasks
7. 18:57Distribution testing without prover
8. 21:55Interactive proofs for distributions
9. 27:17Label-invariant distribution properties
10. 30:48Beyond label-invariant properties
11. 40:41General distribution properties
12. 47:06Interactive proofs for string languages
13. 59:31Summary of results
14. 1:02:27Q&A