1
$\begingroup$

I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006):

Further, it is NP-hard to learn a disjunction of k variables as a disjunction of few than k log n variable.

I believe this is meant in the PAC model, I believe without membership queries.The author states this without proof. This usually means the result is well-known or obvious but I haven't been able to track it down in an online resource (including a few papers surveying the basics) and it lacks citation.

(I asked a simpler question here but this wasn't strong enough to clear up my confusion on the claim in the paper.)

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ What is your question? Have you attempted the proof yourself? $\endgroup$ – Raphael♦ Dec 17 '15 at 20:57
  • $\begingroup$ @Raphael my question is the title, "Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?" Honestly no not really, given that it seems to be a well-known result I thought it would be easily searchable and should be if it's not. I'll spend significant time solving it myself as a last resort, as I believe this is good practice most of the time. $\endgroup$ – djechlin Dec 17 '15 at 22:03
  • $\begingroup$ Well, "why"? Because you can reduce 3-CNF-SAT to it. Not the answer you were looking for, right? ;) As a learner, trying yourself should be your first resort! Our reference question is there to help you with that. $\endgroup$ – Raphael♦ Dec 17 '15 at 22:56
  • $\begingroup$ @Raphael No need to moralize how I should or shouldn't be learning. I'm reading a recent research paper in computational learning theory, should I seriously be penalized for being unsure whether this result can be solved as an exercise, or requires serious machinery that most experts in the field know and I don't? How many hours of work do you suggest before I try researching the answer literally in any other way? $\endgroup$ – djechlin Dec 17 '15 at 23:18
  • $\begingroup$ It is literally at the level of an exercise: see exercise 5 here: cs7545.wordpress.com/lecture-notes/hw3. If you read the lecture notes you should be able to solve this exercise. $\endgroup$ – Yuval Filmus Dec 18 '15 at 1:14

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.