We show that the class of monotone 2^{O(\sqrt{\log n})}-term DNF
formulae can be PAC learned in polynomial time under the uniform
distribution. This is an exponential improvement over previous
algorithms in this model, which could learn monotone
o(\log^2 n)-term DNF, and is the first efficient algorithm
for ...
more >>>
Let \mathcal{M} be a bridgeless matroid on ground set \{1,\ldots, n\} and f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\} be the indicator function of its independent sets. A folklore fact is that f_\mathcal{M} is ``evasive," i.e., D(f_\mathcal{M}) = n where D(f) denotes the deterministic decision tree complexity of f. Here we prove ... more >>>
We study the Fourier spectrum of functions f\colon \{0,1\}^{mk} \to \{-1,0,1\} which can be written as a product of k Boolean functions f_i on disjoint m-bit inputs. We prove that for every positive integer d,
