<p>Does the learning theory community in general believe that juntas can be learned in polynomial time? </p>

<p>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.</p>

<p>Do more than 50% of experts believe that the Junta problem IS solvable in polynomial time?</p>

<p>Thanks.</p>

CC BY-SA 4.0
2020-02-04T21:55:52.923Z
You’re asking about Majority of experts, and your question can be generalized to k-juntas.
Aryeh
CC BY-SA 4.0
2020-02-05T03:36:55.427Z
I would say, people has enough belief in its hardness to base lower bounds (conditional) on it: http://proceedings.mlr.press/v19/feldman11a.html (Theorem 9)
Clement C.
<soft-question><machine-learning><boolean-functions><pac-learning>
Status of the Junta Problem (soft question)
zfkmz
# Status of the Junta Problem (soft question)

(Asked by: username_0 on 2020-02-04)

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.

**Tags:** soft-question, machine-learning, boolean-functions, pac-learning

> **Comments:**
> **username_1**: You’re asking about Majority of experts, and your question can be generalized to k-juntas.  
> **username_2**: I would say, people has enough belief in its hardness to base lower bounds (conditional) on it: http://proceedings.mlr.press/v19/feldman11a.html (Theorem 9)  

---

## 0 answers

