[1]   Noga Alon and Joel H. Spencer: The Probabilistic Method. Wiley, 2nd edition, 2000. [doi:10.1002/0471722154]

[2]   Cem Anil, Guodong Zhang, Yuhuai Wu, and Roger B. Grosse: Learning to give checkable answers with prover-verifier games, 2021. [arXiv:2108.12099]

[3]   Martin Anthony and Peter L. Bartlett: Neural Network Learning: Theoretical Foundations. Cambridge Univ. Press, 2002. [doi:10.1017/CBO9780511624216]

[4]   Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang: Active property testing. In Proc. 53rd FOCS, pp. 21–30. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.64]

[5]   Ran Canetti and Ari Karchmer: Covert learning: How to learn with an untrusted intermediary. In Kobbi Nissim and Brent Waters, editors, Proc. Theory of Cryptography Conf. (TCC’21), pp. 1–31. Springer, 2021. [doi:10.1007/978-3-030-90456-2_1]

[6]   Clément L. Canonne: A short note on learning discrete distributions, 2020. [arXiv:2002.11457]

[7]   Clément L. Canonne: A survey on distribution testing: Your data is big. But is it blue? Theory of Computing Library Graduate Surveys, 9:1–100, 2020. [doi:10.4086/toc.gs.2020.009]

[8]   Clément L. Canonne, Ayush Jain, Gautam Kamath, and Jerry Li: The price of tolerance in distribution testing. In Proc. 35th Ann. Conf. on Learning Theory (COLT’22), pp. 573–624. MLR Press, 2022. PMLR vol. 178.

[9]   Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, and Ryan Sweke: Classical verification of quantum learning. In Proc. 14th Innovations in Theoret. Comp. Sci. Conf. (ITCS’23), pp. 24:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2023. [doi:10.4230/LIPIcs.ITCS.2024.24, arXiv:2306.04843]

[10]   Alessandro Chiesa and Tom Gur: Proofs of proximity for distribution testing. In Proc. 9th Innovations in Theoret. Comp. Sci. Conf. (ITCS’18), pp. 53:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.53]

[11]   John Duchi: Lecture Notes on Statistics and Information Theory, 2024. Available at Stanford. Accessed: 2024-11-26.

[12]   Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth: Preserving statistical validity in adaptive data analysis, 2014. [arXiv:1411.2664]

[13]   Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth: Preserving statistical validity in adaptive data analysis. In Proc. 47th STOC, pp. 117–126. ACM Press, 2015. [doi:10.1145/2746539.2746580]

[14]   Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum: Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1–64, 2015. [doi:10.1145/2699436]

[15]   Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff: Interactive proofs for verifying machine learning. In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 41:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021 (virtual conference). [doi:10.4230/LIPIcs.ITCS.2021.41]

[16]   Moritz Hardt and Jonathan R. Ullman: Preventing false discovery in interactive data analysis is hard. In Proc. 55th FOCS, pp. 454–463. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.55]

[17]   David Haussler: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. Comput., 100(1):78–150, 1992. [doi:10.1016/0890-5401(92)90010-D]

[18]   Tal Herman and Guy N. Rothblum: Verifying the unseen: Interactive proofs for label-invariant distribution properties. In Proc. 54th STOC, pp. 1208–1219. ACM Press, 2022. [doi:10.1145/3519935.3519987]

[19]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statistical Assoc., 58(301):13–30, 1963. [doi:10.2307/2282952]

[20]   Michael J. Kearns: Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983–1006, 1998. [doi:10.1145/293347.293351]

[21]   Michael J. Kearns, Robert E. Schapire, and Linda Sellie: Toward efficient agnostic learning. Machine Learning, 17(2–3):115–141, 1994. [doi:10.1007/BF00993468]

[22]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ε. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03. [doi:10.1016/J.JCSS.2007.06.019]

[23]   Lucien Le Cam: Asymptotic Methods in Statistical Decision Theory. Springer, 1986. [doi:10.1007/978-1-4612-4946-7]

[24]   Saachi Mutreja and Jonathan Shafer: PAC verification of statistical algorithms, 2022. [arXiv:2211.17096v1]

[25]   Saachi Mutreja and Jonathan Shafer: PAC verification of statistical algorithms. In Gergely Neu and Lorenzo Rosasco, editors, Proc. 36th Ann. Conf. on Learning Theory (COLT’23), volume 195, pp. 5021–5043. MLR Press, 2023. PMLR vol. 195.

[26]   Michael Ngo and Michael P. Kim: Publicly-verifiable certificates for statistical algorithms, 2026. Unpublished manuscript, see blog post.

[27]   Liam Paninski: A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inform. Theory, 54(10):4750–4755, 2008. [doi:10.1109/TIT.2008.928987]

[28]   Alfréd Rényi: On measures of entropy and information. In Jerzy Neyman, editor, Proc. 4th Berkeley Symp. on Math. Statistics and Probability, Vol. 1: Contributions to the Theory of Statistics, volume 4, pp. 547–561. Univ. California Press, 1961. Available at Project Euclid.

[29]   Sebastien Roch: Modern Discrete Probability: An Essential Toolkit. Cambridge Univ. Press, 2023. [doi:10.1017/9781009305129]

[30]   Ronitt Rubinfeld and Arsen Vasilyan: Testing distributional assumptions of learning algorithms. In Proc. 55th STOC, pp. 1643–1656. ACM Press, 2023. [doi:10.1145/3564246.3585117, arXiv:2204.07196]

[31]   Sanjit A. Seshia, Dorsa Sadigh, and S. Shankar Sastry: Toward verified artificial intelligence. Comm. ACM, 65(7):46–55, 2022. [doi:10.1145/3503914]

[32]   Shai Shalev-Shwartz and Shai Ben-David: Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, 2014. [doi:doi.org/10.1017/CBO9781107298019]

[33]   Thomas Steinke and Jonathan R. Ullman: Interactive fingerprinting codes and the hardness of preventing false discovery. In Proc. 28th Ann. Conf. on Learning Theory (COLT’15), pp. 1588–1628. Springer, 2015. PMLR vol. 40.

[34]   Michel Talagrand: Sharper bounds for Gaussian and empirical processes. Ann. Probab., 22(1):28–76, 1994. [doi:10.1214/aop/1176988847]

[35]   Leslie G. Valiant: A theory of the learnable. Comm. ACM, 27(11):1134–1142, 1984. [doi:10.1145/1968.1972]

[36]   Vladimir N. Vapnik and Alexei Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Appl., 16(2):264–280, 1971. Russian original at Teor. Veroyatnostei i ee Primeneniya. Preliminary version in Dokl. Akad. Nauk SSSR 181 (1968), 781–783. [doi:10.1137/1116025]

[37]   Bin Yu: Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam: Research papers in probability and statistics, pp. 423–435. Springer, 1997. [doi:10.1007/978-1-4612-1880-7_29]