A neural network is said to be nonoverlapping if there is at most one edge outgoing from each node. We investigate the number of examples that a learning algorithm needs when using nonoverlapping neural networks as hypotheses. We derive bounds for this sample complexity in terms of the Vapnik-Chervonenkis dimension. ... more >>>

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 monotone $(\log n)^{\omega(1)}$-term ... more >>>

We prove two lower bounds on the Statistical Query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension $d$, a running time of $\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is defined to be the maximum number ... more >>>

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time ... more >>>

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning? Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

The threshold degree of a Boolean function $f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We construct two halfspaces on $\{0,1\}^n$ whose intersection has threshold degree $\Theta(\sqrt n),$ an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and ... more >>>

The threshold degree of a function $f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We prove that the intersection of two halfspaces on $\{0,1\}^n$ has threshold degree $\Omega(n),$ which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best ... more >>>