Multilinear Extensions

For any -variate polynomial polynomial, it's multilinear extension is the polynomial which agrees over all points : . By the Schwartz-Zippel lemma, if and disagree at even a single input, then and must disagree almost everywhere.

For more precise details please read Section 3.5 of Proofs and Args ZK.


In practice, MLE's are stored as the vector of evaluations over the -variate boolean hypercube . There are two important algorithms over multilinear extensions: single variable binding, and evaluation.

Single Variable Binding

With a single streaming pass over all evaluations we can "bind" a single variable of the -variate multilinear extension to a point . This is a critical sub-algorithm in sumcheck. During the binding the number of evaluation points used to represent the MLE gets reduced by a factor of 2:

  • Before:
  • After:

Assuming your MLE is represented as a 1-D vector of evaluations over the -variate boolean hypercube , indexed little-endian

Then we can transform the vector representing the transformation from by "binding" the evaluations vector to a point .

let n = 2^v;
let half = n / 2;
for i in 0..half {
    let low = E[i];
    let high = E[half + i];
    E[i] = low + r * (high - low);

Multi Variable Binding

Another common algorithm is to take the MLE and compute its evaluation at a single -variate point outside the boolean hypercube . This algorithm can be performed in time by preforming the single variable binding algorithm times. The time spent on 'th variable binding is , so the total time across all bindings is proportional to .