Hardness of Learning DNFs using Halfspaces

Suprovat Ghoshal, Rishi Saket

The problem of learning $t$-term DNF formulas (for $t=O(1)$) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A $t$-term DNF can be ef…