Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta problem in nearly O(n^(2logn/3)) time, which as far as I can tell is the best upper bound today.
Do more than 50% of experts believe that the Junta problem IS solvable in polynomial time?
Thanks.