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?

  • 2
    $\begingroup$ This survey by L. Hellerstein and R. Servedio covers more examples of learning algorithms using the same strategy. $\endgroup$ Commented Feb 13, 2018 at 18:02
  • $\begingroup$ See also this survey by de Wolf (esp. Section 3.3). $\endgroup$
    – Clement C.
    Commented Feb 13, 2018 at 18:09
  • $\begingroup$ Thanks! (@ClementC. I dont see any bounding of the approximate degree going on in your reference. What am I missing?) $\endgroup$ Commented Feb 13, 2018 at 21:38
  • $\begingroup$ You're probably not missing anything; I must have. $\endgroup$
    – Clement C.
    Commented Feb 13, 2018 at 21:40
  • 1
    $\begingroup$ Now, again based on your last comment, this seems relevant: cstheory.stackexchange.com/questions/21916/… $\endgroup$
    – Clement C.
    Commented Feb 18, 2018 at 5:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.