• Terminology: Given an -variate polynomial
    • The degree of a term is the sum of the exponents in the term
    • The total degree of a is the maximum of the degrees of the term

Let be any field, and let be a nonzero -variate polynomial of total degree at most . Then on any finite set ,

Here, denotes an drawn uniformly at random from the product set , and denotes the size of .