4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You’re asking about Majority of experts, and your question can be generalized to k-juntas. $\endgroup$ – Aryeh Feb 4 '20 at 21:55
  • $\begingroup$ I would say, people has enough belief in its hardness to base lower bounds (conditional) on it: proceedings.mlr.press/v19/feldman11a.html (Theorem 9) $\endgroup$ – Clement C. Feb 5 '20 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.