<p>This paper (<a href="http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf" rel="nofollow noreferrer">http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf</a>) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean function into a learning algorithm. </p>

<p>Have there been other works in this line? What are the most recent things we know about such conversion from approximate degree to learning algorithms? </p>

CC BY-SA 3.0
2018-02-13T18:02:38.670Z
[This survey by L. Hellerstein and R. Servedio](http://www.cs.columbia.edu/~rocco/Public/hs6.pdf) covers more examples of learning algorithms using the same strategy.
Robin Kothari
CC BY-SA 3.0
2018-02-13T18:09:30.653Z
See also [this survey](https://theoryofcomputing.org/articles/gs001/) by de Wolf (esp. Section 3.3).
Clement C.
CC BY-SA 3.0
2018-02-13T21:38:40.477Z
Thanks! (@ClementC. I dont see any bounding of the approximate degree going on in your reference. What am I missing?)
gradstudent
CC BY-SA 3.0
2018-02-13T21:40:29.983Z
You're probably not missing anything; I must have.
Clement C.
CC BY-SA 3.0
2018-02-15T02:13:13.787Z
Thanks! Let me just use this discussion thread to ask a related thing : So approximate degree of Majority seems to be $\Omega(n)$ and hence that implies that LTF circuits can never have a small approximate degree. Right? So does that also mean that there cant be fast learning algorithms for LTF circuit classes? What is the best we know of about this for this specific case?
gradstudent
CC BY-SA 3.0
2018-02-18T03:57:28.813Z
@gradstudent Not sure I understand your question. Are you asking if the class of Boolean functions which can be represented by halfspaces is efficiently PAC-learnable? (If so, yes, this follows from a VC dimension argument)
Clement C.
CC BY-SA 3.0
2018-02-18T05:31:12.353Z
I am talking of any class of functions which is representable by some LTF circuits. Say "all Boolean functions representable by size s depth 2 LTF circuits" for some s. (...not sure why you thought of half-spaces..)
gradstudent
CC BY-SA 3.0
2018-02-18T05:51:34.183Z
@gradstudent because the terms LTFs (Linear Threshold Functions) and halfspaces are  synonymous (cf. e.g. [Section 3 of these lecture notes](https://www.cs.utexas.edu/~klivans/lec3.pdf)), and I was not familiar with the use of "LTF circuit" for *circuit with threshold gates*.
Clement C.
CC BY-SA 3.0
2018-02-18T05:55:34.810Z
Now, again based on your last comment, this seems relevant: https://cstheory.stackexchange.com/questions/21916/on-the-status-of-learnability-inside-mathsftc0
Clement C.
CC BY-SA 3.0
2018-02-18T09:01:17.753Z
That discussion does seem close to what I am looking for. But I dont see any references shared there about fastest running times for learning this class $TC^0$. Any?
gradstudent
<cc.complexity-theory><reference-request><boolean-functions><lg.learning><pac-learning>
Reference request for the relationship between approximating degree of Boolean functions and learning algorithms
gradstudent
# Reference request for the relationship between approximating degree of Boolean functions and learning algorithms

(Asked by: username_0 on 2018-02-13)

This paper (<http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf>) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean function into a learning algorithm.

Have there been other works in this line? What are the most recent things we know about such conversion from approximate degree to learning algorithms?

**Tags:** cc.complexity-theory, reference-request, boolean-functions, lg.learning, pac-learning

> **Comments:**
> **username_1**: [This survey by L. Hellerstein and R. Servedio](http://www.cs.columbia.edu/~rocco/Public/hs6.pdf) covers more examples of learning algorithms using the same strategy.  
> **username_2**: See also [this survey](https://theoryofcomputing.org/articles/gs001/) by de Wolf (esp. Section 3.3).  
> **username_0**: Thanks! (@ClementC. I dont see any bounding of the approximate degree going on in your reference. What am I missing?)  
> **username_2**: You're probably not missing anything; I must have.  
> **username_0**: Thanks! Let me just use this discussion thread to ask a related thing : So approximate degree of Majority seems to be $\Omega(n)$ and hence that implies that LTF circuits can never have a small approximate degree. Right? So does that also mean that there cant be fast learning algorithms for LTF circuit classes? What is the best we know of about this for this specific case?  
> **username_2**: @username_0 Not sure I understand your question. Are you asking if the class of Boolean functions which can be represented by halfspaces is efficiently PAC-learnable? (If so, yes, this follows from a VC dimension argument)  
> **username_0**: I am talking of any class of functions which is representable by some LTF circuits. Say "all Boolean functions representable by size s depth 2 LTF circuits" for some s. (...not sure why you thought of half-spaces..)  
> **username_2**: @username_0 because the terms LTFs (Linear Threshold Functions) and halfspaces are  synonymous (cf. e.g. [Section 3 of these lecture notes](https://www.cs.utexas.edu/~klivans/lec3.pdf)), and I was not familiar with the use of "LTF circuit" for *circuit with threshold gates*.  
> **username_2**: Now, again based on your last comment, this seems relevant: https://cstheory.stackexchange.com/questions/21916/on-the-status-of-learnability-inside-mathsftc0  
> **username_0**: That discussion does seem close to what I am looking for. But I dont see any references shared there about fastest running times for learning this class $TC^0$. Any?  

---

## 0 answers

