On representations by low-degree polynomials

In the first part of the paper we show that a subset S of a boolean cube B_n embedded in the projective space Pⁿ can be approximated by a subset of B_n defined by nonzeroes of a low-degree polynomial only if the values of the Hilbert function of S are sufficiently small relative to the size of S. The use of this property provides a simple and direct technique for proving lower bounds on the size of ACC[p^r] circuits. In the second part we look at the problem of computing many-output function by ACC[p^r] circuit and give an example when such a circuit can be correct only at exponentially small fraction of assignments