Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

This paper studies the learnability of branching programs and small depth

circuits with modular and threshold gates in both the exact and PAC learning

models with and without membership queries. Some of the results extend earlier

works in [GG95,ERR95,BTW95]. The main results are as follows. For

branching programs we ...
more >>>

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Parikshit Gopalan, Subhash Khot, Rishi Saket

We study the polynomial reconstruction problem for low-degree

multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ...
more >>>