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.)

  • 1
    $\begingroup$ What is your question? Have you attempted the proof yourself? $\endgroup$
    – Raphael
    Dec 17, 2015 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, 2015 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, 2015 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, 2015 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$ Dec 18, 2015 at 1:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.