We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

We consider the univariate polynomial f_d:=(x+1)^d when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is \Omega(d) for f_d.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

We study the query complexity of one-sided \epsilon-testing the class of Boolean functions f:F^n\to \{0,1\} that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where F is any finite field. We give a polynomial-time \epsilon-testers that ask \tilde O(1/\epsilon) queries. This improves the query complexity \tilde O(|F|/\epsilon) ... more >>>