Submit progress

on Missing Information Impediments to Learnability

The statement

Problem3 [open] Problem 3: Is the concept class C of 2-CNFs consistently learnable by a hypothesis class H? Is the question true for any concept class of formulas that are not modularly evaluatable?

Problem4 [open] Problem 4: Is the concept class C of 3-CNFs consistently learnable by a hypothesis class H? Is the question true for any concept class of formulas that are not efficiently evaluatable?

Problem6 [open] Problem 6: Is the concept class C that comprises either parities or monotone-term 1-decision lists consistently learnable by a hypothesis class H that differs from C?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.