- 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 .