<p>Is there any connection between Interactive proofs and learning theory?</p>

CC BY-SA 3.0
2014-02-12T15:31:56.267Z
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.
Arnab
CC BY-SA 3.0
2014-02-12T00:19:59.163Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-02-12T02:32:52.937Z
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
Clement C.
<lg.learning><interactive-proofs>
Learning theory vs. Interactive Proofs
Arnab
# Learning theory vs. Interactive Proofs

(Asked by: username_0 on 2014-02-11)

Is there any connection between Interactive proofs and learning theory?

**Tags:** lg.learning, interactive-proofs

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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  
> **username_0**: 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.  

---

## 0 answers

