# Multilinear Extensions

For any $v$-variate polynomial $g(x_{1},...x_{v})$ polynomial, it's multilinear extension $f(x_{1},...x_{v})$ is the polynomial which agrees over all $2_{v}$ points $x∈{0,1}_{v}$: $g(x_{1},...x_{v})=f~ (x_{1},...x_{v})∀x∈{0,1}_{v}$. By the Schwartz-Zippel lemma, if $g$ and $f$ disagree at even a single input, then $g$ and $f$ must disagree *almost everywhere*.

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

## Engineering

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

### Single Variable Binding

With a single streaming pass over all $n$ evaluations we can "bind" a single variable of the $v$-variate multilinear extension to a point $r$. 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:**$f~ (x_{1},...x_{v}):{0,1}_{v}→F$**After:**$f_{′}~ (x_{1},...x_{v−1})=f~ (r,x_{1},...x_{v−1}):{0,1}_{v−1}→F$

Assuming your MLE is represented as a 1-D vector of $2_{v}$ evaluations $E$ over the $v$-variate boolean hypercube ${0,1}_{v}$, indexed little-endian

- $E[1]=f~ (0,0,0,1)$
- $E[5]=f~ (0,1,0,1)$
- $E[8]=f~ (1,0,0,0)$

Then we can transform the vector $E→E_{′}$ representing the transformation from $f~ (x_{1},...x_{v})→f_{′}~ (r,x_{1},...x_{v−1})$ by "binding" the evaluations vector to a point $r$.

```
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 $f~ (x_{1},...x_{v})$ and compute its evaluation at a single $v$-variate point outside the boolean hypercube $x∈F_{v}$. This algorithm can be performed in $O(n)$ time by preforming the single variable binding algorithm $g(n)$ times. The time spent on $i$'th variable binding is $O(n/2_{i})$, so the total time across all $gn$ bindings is proportional to $∑_{i=1}n/2_{i}=O(n)$.