Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Nader H. Bshouty, George Haddad

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approxi…