Is there any connection between Interactive proofs and learning theory?

  • 4
    $\begingroup$ This is a rather open-ended question. Maybe you could be more specific about what you're thinking of ? After all, a trivial answer is "no, because an interactive proof is a protocol and learning theory is a collection of results", but I doubt that's what you're asking. $\endgroup$ – Suresh Venkat Feb 12 '14 at 0:19
  • 6
    $\begingroup$ There seems to be a connection between Zero-Knowledge proofs and hardness of PAC-learning, see for instance [Xiao09] (I am too hazy on the subject to summarize or give a reliable account of the said connection). -- [Xia09] Xiao, D., "On Basing ZK ≠ BPP on the Hardness of PAC Learning," Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on , vol., no., pp.304,315, 15-18 July 2009 doi: 10.1109/CCC.2009.11 $\endgroup$ – Clement C. Feb 12 '14 at 2:32
  • $\begingroup$ Suresh, you're absolutely right, the question is indeed open ended. But if someone asked a similar open-ended question - "is there a connection between representation theory and computational complexity" - say thirty or forty years ago, the trivial answer probably would have been "no". I'm a bit unsure myself on what I am looking for, but I think what Clement suggested (Thank you, Clement), maybe a great starting point. $\endgroup$ – Arnab Feb 12 '14 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.