Interactive proofs for verifying machine learning

DOI10.4230/LIPICS.ITCS.2021.41MaRDI QIDQ7229328zbMATH OpenFDO

Authors Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.41

zbMATH Keywords

PAC learningcomplexity lower boundsdistribution testingFourier analysis of Boolean functionsGoldreich-Levin algorithmKushilevitz-Mansour algorithmcomplexity gaps

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• A theory of the learnable
• Active property testing
• Constant depth circuits, Fourier transform, and learnability
• Delegating computation: interactive proofs for muggles
• Learning Decision Trees Using the Fourier Spectrum
• Learning regular sets from queries and counterexamples
• Noise-tolerant learning, the parity problem, and the statistical query model
• Proofs of proximity for distribution testing
• Property testing and its connection to learning and approximation
• Pseudorandom functions in almost constant depth from low-noise LPN
• Testing problems with sublearning sample complexity
• The Knowledge Complexity of Interactive Proof Systems
• Tolerant property testing and distance approximation

This page was built for publication: Interactive proofs for verifying machine learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229328)