Multilinear Extension (MLE)

Taken from: Oleg Fomenko and Anton Levochko: Understanding Lasso - A Novel Lookup Argument Protocol

---

We say that $\tilde{f}:{\mathbb{F}}^{\ell }\to \mathbb{F}$ extends $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ if $\tilde{f}(x)=f(x)$ for all $x\in \{0,1{\}}^{\ell }$.

The total degree of an $\ell$-variate polynomial $f$ refers to the maximum sum of the exponents in any monomial of $f$. Observe that if the $\ell$-variate polynomial $f$ is multilinear, then its total degree is at most $\ell$.

It is well-known that for any $f$, there is a unique multilinear polynomial $\tilde{f}$ that extends $f$. The polynomial $\tilde{f}$ is referred to as the multilinear extension (MLE) of $f$.

A particular multilinear extension that arises frequently in the design of proof systems is $\widetilde{\text{eq}}$, which is the MLE of the function $\text{eq}:\{0,1{\}}^{\ell }\times \{0,1{\}}^{\ell }\to \mathbb{F}$ defined in Equation (1).

An explicit expression for $\widetilde{\text{eq}}$ is:

$$\widetilde{\text{eq}}(x,e)=\prod _{i=1}^{\ell }\left(x_i{e}_i+(1-x_i)(1-e_i)\right)\text{\hspace{1em}(2)}$$

Indeed, one can easily check that the right-hand side of Equation (2) is a multilinear polynomial, and that if evaluated at any input $(x,e)\in \{0,1{\}}^{\ell }\times \{0,1{\}}^{\ell }$, it outputs $1$ if $x=e$ and $0$ otherwise. Hence, the right-hand side of Equation (2) is the unique multilinear polynomial extending $\text{eq}$.

Equation (2) implies that $\widetilde{\text{eq}}(r_1,r_2)$ can be evaluated at any point $(r_1,r_2)\in {\mathbb{F}}^{\ell }\times {\mathbb{F}}^{\ell }$ in $\mathcal{O}(\ell )$ time.

This polynomial is also called a Lagrange basis polynomial for $\ell$-variate multilinear polynomials.