# Boolean functions with high query complexity for PAC learning

The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier weights are concentrated on some modes can be PAC learnt in polynomial time. Also it trivially follows that in $2^n$ queries one can learn any Boolean function on the $n-$Hamming cube.

My question is two fold,

• For what concept classes do we know of high ($2^n$?) query lowerbound for PAC learning? If the proof is short then it would be very helpful if you could kindly type it in or give a reference.

• For Boolean functions whose Fourier spectrum seems very evenly spread out over the modes it seems that it should be hard to learn them in a few queries. Is this intuition right and if yes then what is the most quantitative theorem we know of which captures this?

I am interchangeably using the words "query complexity" and "running time of the learning algorithm". I hope this is okay. If not then it would be helpful if you could point out the subtlety that I am missing.

• Do you want explicit, structured classes of functions? Clearly, if you take the class of all $n$-variate Boolean functions, you'll get what you want, otherwise. (Also, since you are talking about PAC learning, I assume that by "queries" you mean "samples" -- in which case you should have a $2^n/\varepsilon$ dependence in your complexity?) Finally, regarding the "subtlety" between sample/query complexity and time complexity: 3-term DNF formulae are not properly efficiently learnable (i.e., with polynomial time complexity) unless RP=NP, yet they can be "improperly" learned efficiently. – Clement C. Jun 29 '17 at 20:11
• (that is, the number of samples information-theoretically sufficient to is polynomial, but after that hell breaks loose in processing time if you want to output a hypothesis which is a 3-term DNF as well) – Clement C. Jun 29 '17 at 20:15
• Can you give me a reference for a proof about this result about $3-$term DNF? (Why is $3$ special?) About my first question I am thinking of examples of what might be the hardest Boolean functions to learn. What do we know best in this direction? – gradstudent Jun 29 '17 at 20:20
• For the 3-term DNF, look at An Introduction to Computational Learning Theory, by Kearns and Vazirani (MIT Press, 1994). This is Section 1.4 (Theorem 1.3). (Incidentally, that is a great book to read.) The $3$ is special for a reduction to 3-coloring. – Clement C. Jun 29 '17 at 20:23
• Thanks! (About $k-$DNF there is an unanswered question lying here, cstheory.stackexchange.com/questions/12225/… ) So about the functions which are hardest to PAC learn, what is known? (..like shouldn't the inner-product-mod-2 be a very hard function to learn?..) – gradstudent Jun 29 '17 at 20:35