If you’re familiar with the Lagrange interpolation, you may know that it is used to construct the interpolation polynomial for a set of points in one dimension and if you’re not, no worries you can just watch these two videos (Video 1, Video 2) before proceeding. Our main focus today is using Lagrange interpolation in multilinear extensions. Don’t be overwhelmed by the upcoming formulas, you only need to understand what they do. We will provide you with a much simpler formula to use when dealing with MLEs at the end of the article, after understanding everything.

The formulation of the multilinear extension can be thought of as a multi-dimensional extension of the Lagrange interpolation formula. The idea is to maintain the properties of the function at the vertices while allowing for interpolation within the entire hypercube.

Given as input all $2^l$ evaluations of a function $f: { 0,1 }^l → \mathbb{F}$, for any point $r \in \mathbb{F}^l$ there is an $O(2^l)$-time algorithm for evaluating $\tilde{f}(r)$.

Multilinear Extension Formula:

$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

where $\tilde{\delta}_w(r)$ is the Multilinear Lagrange basis Polynomial corresponding to $w$ :

$$\tilde{\delta}w(r) = \Pi{i=1}^l(r_iw_i + (1-r_i)(1-w_i))$$

The formula $\tilde{\delta}_w(r)$ is part of a multilinear extension (MLE), which allows us to extend a function defined on binary inputs to work with real inputs between 0 and 1.

It works by multiplying together simple terms that either "pick" $r_i​$or $1− r_i​,$ depending on whether the binary value $w_i$ is 1 or 0. This product ensures a smooth transition between the values at each binary point. Essentially, it blends between these binary points based on the real values of $r$, allowing us to interpolate the function over continuous inputs.

If you still don’t understand how it works, no worries you don’t need to. Just keep going and you’ll get a much simpler formula that you can use easily at the end.

• Basis Structure: $\tilde{\delta}_w(r)$​, can be seen as a generalization of Lagrange basis polynomials. They ensure that at each vertex $r​$, the extension matches the value of $f(r_i)$, similar to how Lagrange interpolation ensures the polynomial passes through each point.

A Boolean hypercube is a geometric representation of all possible binary values ${0, 1}$ in n-dimensional space. Each vertex of the hypercube corresponds to an n-length binary string, and there are $2^𝑛$ n vertices in total, representing all possible combinations of 0 and 1.

For example:

• In a 1-dimensional Boolean hypercube, you have 2 vertices: $0$ and $1$, which is just a line.

• In a 2-dimensional Boolean hypercube, you have 4 vertices: $(0,0),(0,1),(1,0),(1,1)$, forming a square.

• In a 3-dimensional Boolean hypercube, you have 8 vertices:$(000),(001),(010),(011),(100),(101),(110),(111),$ forming a cube.

In ZKPs, you often need to work with functions that are defined over binary inputs. For instance, a function $f$ might be defined on inputs of length $n$ that are either 0 or 1, meaning $f$ is naturally defined on the vertices of a Boolean hypercube of dimension $n$. So a Boolean Hypercube is another way of describing our multivariate function.

• Building the Formula

  • Choose the points for interpolation: For bilinear interpolation in two dimensions, you generally have four points:

    • $v_0 = (x_{v_0},y_{v0})$

$L_0(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_1})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_0}-x_{v_1})(x_{v_0}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_1})(\textcolor{skyblue}{x_2} -y_{v_2})}{(y_{v_0} -y_{v_1})((y_{v_0}-y_{v_2})}$

$L_1(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_1}-x_{v_0})(x_{v_1}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_2})}{(y_{v_1} -y_{v_0})((y_{v_1}-y_{v_2})}$

$L_2(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_2}-x_{v_0})(x_{v_2}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_2} -y_{v_0})((y_{v_2}-y_{v_1})}$

$L_3(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_3}-x_{v_0})(x_{v_3}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_3} -y_{v_0})((y_{v_3}-y_{v_1})}$

Each $L_i(x,y)$ equals 1 at vertex $v_i$ and 0 at the other vertices meaning:

• $L_0(x_1,x_2)$ is 1 when $$𝑥1 ​ = x{v_0}$​and$𝑥2 ​ = y{v_0}$, and 0 when either$𝑥

$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}L_0(x_1,x_2) + \textcolor{skyblue}{f(v_1)}L_1(x_1,x_2) + \textcolor{skyblue}{f(v_2)}L_2(x_1,x_2) + \textcolor{skyblue}{f(v_3)}L_3(x_1,x_2)$

• Final Formula (Simplified):

$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}(1-x_1)(1-x_2) + \textcolor{skyblue}{f(v_1)}(1-x_1)x_2 + \textcolor{skyblue}{f(v_2)}x_1 (1-x_2) + \textcolor{skyblue}{f(v_3)}x_1x_2$

You only need to understand this formula when dealing with MLEs without going through all of the math behind it.

$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

So the Final Formula is basically this formula but written in a more elegant way.

We define a bivariate function over the domain ${ 0,1 }^l$ :

$f(0,0)= 1 \space \space \space \space f(0,1) = 2 \space \space \space \space f(1,0) = 8 \space \space \space \space f(1,1) = 10$

The MLE of the bivariate function will look like this:

$\tilde{f}(x_1,x_2) =\textcolor{skyblue}{1}(1-x_1)(1-x_2) + \textcolor{skyblue}{2}(1-x_1)x_2 + \textcolor{skyblue}{8}x_1 (1-x_2) + \textcolor{skyblue}{10}x_1x_2$

which we can simplify it to:

$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$

Notice that each of the four terms on the right hand side of the equation ensures that the MLE evaluates equally to our predefined values for the bivariate function:

$f(0,0) = \tilde{f}(0,0) = \textcolor{skyblue}{1}⋅1 + 2⋅0 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{1}$

$f(0,1) = \tilde{f}(0,1) = 1⋅0 + \textcolor{skyblue}{2}⋅1 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{2}$

$f(1,0) = \tilde{f}(1,0) = 1⋅0 + 2⋅0 + \textcolor{skyblue}{8}⋅1 + 10⋅0 = \textcolor{skyblue}{8}$

$f(1,1) = \tilde{f}(1,1) = 1⋅0 + 2⋅0 + 8⋅0 + \textcolor{skyblue}{10}⋅1 = \textcolor{skyblue}{10}$

So our MLE looks like this:

By replacing $x_1$ and $x_2$ in $\tilde{f}(x_1,x_2)$ by the indexes (4,5) we will get 54 which is the most bottom right cell.

$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$

$\tilde{f}(5,5) = 1 + 7⋅4 + 5 + 4⋅5 = 1 + 28 + 5 + 20 = 54$

$Formula \space 1: \space \space \space \space \tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

$Formula \space 2: \space \space \space \space \tilde{f}(x_1,x_2) = {f(v_0)}(1-x_1)(1-x_2) + {f(v_1)}(1-x_1)x_2 + {f(v_2)}x_1 (1-x_2) + {f(v_3)}x_1x_2$

Both of these formulas represent multilinear extensions (MLE) of a Boolean function defined on binary points like ${0,1}$ to a continuous domain.

The first formula is the general case for an $l$-dimensional Boolean function, where you're summing over all possible binary vectors $𝑤 ∈ {0 , 1}^l$ .

The second formula is the specific bivariate (2-dimensional) case, where $l=2$, and you're interpolating between the four possible binary inputs $(0,0),(0,1),(1,0),(1,1)$ as we saw in the previous example.

This is all you need to know about Multi-dimensional Lagrange Interpolation for Multilinear extensions. Hope this article was helpful. The next article will be a full guide on the sumcheck protocol. We’ll be applying everything we’ve learned so far.

If you’re familiar with the Lagrange interpolation, you may know that it is used to construct the interpolation polynomial for a set of points in one dimension and if you’re not, no worries you can just watch these two videos (Video 1, Video 2) before proceeding. Our main focus today is using Lagrange interpolation in multilinear extensions. Don’t be overwhelmed by the upcoming formulas, you only need to understand what they do. We will provide you with a much simpler formula to use when dealing with MLEs at the end of the article, after understanding everything.

The formulation of the multilinear extension can be thought of as a multi-dimensional extension of the Lagrange interpolation formula. The idea is to maintain the properties of the function at the vertices while allowing for interpolation within the entire hypercube.

Given as input all $2^l$ evaluations of a function $f: { 0,1 }^l → \mathbb{F}$, for any point $r \in \mathbb{F}^l$ there is an $O(2^l)$-time algorithm for evaluating $\tilde{f}(r)$.

Multilinear Extension Formula:

$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

where $\tilde{\delta}_w(r)$ is the Multilinear Lagrange basis Polynomial corresponding to $w$ :

$$\tilde{\delta}w(r) = \Pi{i=1}^l(r_iw_i + (1-r_i)(1-w_i))$$

The formula $\tilde{\delta}_w(r)$ is part of a multilinear extension (MLE), which allows us to extend a function defined on binary inputs to work with real inputs between 0 and 1.

It works by multiplying together simple terms that either "pick" $r_i​$or $1− r_i​,$ depending on whether the binary value $w_i$ is 1 or 0. This product ensures a smooth transition between the values at each binary point. Essentially, it blends between these binary points based on the real values of $r$, allowing us to interpolate the function over continuous inputs.

If you still don’t understand how it works, no worries you don’t need to. Just keep going and you’ll get a much simpler formula that you can use easily at the end.

• Basis Structure: $\tilde{\delta}_w(r)$​, can be seen as a generalization of Lagrange basis polynomials. They ensure that at each vertex $r​$, the extension matches the value of $f(r_i)$, similar to how Lagrange interpolation ensures the polynomial passes through each point.

A Boolean hypercube is a geometric representation of all possible binary values ${0, 1}$ in n-dimensional space. Each vertex of the hypercube corresponds to an n-length binary string, and there are $2^𝑛$ n vertices in total, representing all possible combinations of 0 and 1.

For example:

• In a 1-dimensional Boolean hypercube, you have 2 vertices: $0$ and $1$, which is just a line.

• In a 2-dimensional Boolean hypercube, you have 4 vertices: $(0,0),(0,1),(1,0),(1,1)$, forming a square.

• In a 3-dimensional Boolean hypercube, you have 8 vertices:$(000),(001),(010),(011),(100),(101),(110),(111),$ forming a cube.

In ZKPs, you often need to work with functions that are defined over binary inputs. For instance, a function $f$ might be defined on inputs of length $n$ that are either 0 or 1, meaning $f$ is naturally defined on the vertices of a Boolean hypercube of dimension $n$. So a Boolean Hypercube is another way of describing our multivariate function.

• Building the Formula

  • Choose the points for interpolation: For bilinear interpolation in two dimensions, you generally have four points:

    • $v_0 = (x_{v_0},y_{v0})$

$L_0(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_1})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_0}-x_{v_1})(x_{v_0}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_1})(\textcolor{skyblue}{x_2} -y_{v_2})}{(y_{v_0} -y_{v_1})((y_{v_0}-y_{v_2})}$

$L_1(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_2})}{(x_{v_1}-x_{v_0})(x_{v_1}-x_{v_2})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_2})}{(y_{v_1} -y_{v_0})((y_{v_1}-y_{v_2})}$

$L_2(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_2}-x_{v_0})(x_{v_2}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_2} -y_{v_0})((y_{v_2}-y_{v_1})}$

$L_3(\textcolor{skyblue}{x_1,x_2}) = \frac{(\textcolor{skyblue}{x_1}-x_{v_0})((\textcolor{skyblue}{x_1}-x_{v_1})}{(x_{v_3}-x_{v_0})(x_{v_3}-x_{v_1})} ⋅ \frac{(\textcolor{skyblue}{x_2} -y_{v_0})(\textcolor{skyblue}{x_2}-y_{v_1})}{(y_{v_3} -y_{v_0})((y_{v_3}-y_{v_1})}$

Each $L_i(x,y)$ equals 1 at vertex $v_i$ and 0 at the other vertices meaning:

• $L_0(x_1,x_2)$ is 1 when $$𝑥1 ​ = x{v_0}$​and$𝑥2 ​ = y{v_0}$, and 0 when either$𝑥

$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}L_0(x_1,x_2) + \textcolor{skyblue}{f(v_1)}L_1(x_1,x_2) + \textcolor{skyblue}{f(v_2)}L_2(x_1,x_2) + \textcolor{skyblue}{f(v_3)}L_3(x_1,x_2)$

• Final Formula (Simplified):

$\tilde{f}(x_1,x_2) = \textcolor{skyblue}{f(v_0)}(1-x_1)(1-x_2) + \textcolor{skyblue}{f(v_1)}(1-x_1)x_2 + \textcolor{skyblue}{f(v_2)}x_1 (1-x_2) + \textcolor{skyblue}{f(v_3)}x_1x_2$

You only need to understand this formula when dealing with MLEs without going through all of the math behind it.

$\tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

So the Final Formula is basically this formula but written in a more elegant way.

We define a bivariate function over the domain ${ 0,1 }^l$ :

$f(0,0)= 1 \space \space \space \space f(0,1) = 2 \space \space \space \space f(1,0) = 8 \space \space \space \space f(1,1) = 10$

The MLE of the bivariate function will look like this:

$\tilde{f}(x_1,x_2) =\textcolor{skyblue}{1}(1-x_1)(1-x_2) + \textcolor{skyblue}{2}(1-x_1)x_2 + \textcolor{skyblue}{8}x_1 (1-x_2) + \textcolor{skyblue}{10}x_1x_2$

which we can simplify it to:

$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$

Notice that each of the four terms on the right hand side of the equation ensures that the MLE evaluates equally to our predefined values for the bivariate function:

$f(0,0) = \tilde{f}(0,0) = \textcolor{skyblue}{1}⋅1 + 2⋅0 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{1}$

$f(0,1) = \tilde{f}(0,1) = 1⋅0 + \textcolor{skyblue}{2}⋅1 + 8⋅0 + 10⋅0 = \textcolor{skyblue}{2}$

$f(1,0) = \tilde{f}(1,0) = 1⋅0 + 2⋅0 + \textcolor{skyblue}{8}⋅1 + 10⋅0 = \textcolor{skyblue}{8}$

$f(1,1) = \tilde{f}(1,1) = 1⋅0 + 2⋅0 + 8⋅0 + \textcolor{skyblue}{10}⋅1 = \textcolor{skyblue}{10}$

So our MLE looks like this:

By replacing $x_1$ and $x_2$ in $\tilde{f}(x_1,x_2)$ by the indexes (4,5) we will get 54 which is the most bottom right cell.

$\tilde{f}(x_1,x_2) = 1+ 7x_1 + x_2 + x_1x_2$

$\tilde{f}(5,5) = 1 + 7⋅4 + 5 + 4⋅5 = 1 + 28 + 5 + 20 = 54$

$Formula \space 1: \space \space \space \space \tilde{f}(r) = \sum_{w \in { 0,1 }^l} f(w)⋅ \tilde{\delta}_w(r)$

$Formula \space 2: \space \space \space \space \tilde{f}(x_1,x_2) = {f(v_0)}(1-x_1)(1-x_2) + {f(v_1)}(1-x_1)x_2 + {f(v_2)}x_1 (1-x_2) + {f(v_3)}x_1x_2$

Both of these formulas represent multilinear extensions (MLE) of a Boolean function defined on binary points like ${0,1}$ to a continuous domain.

The first formula is the general case for an $l$-dimensional Boolean function, where you're summing over all possible binary vectors $𝑤 ∈ {0 , 1}^l$ .

The second formula is the specific bivariate (2-dimensional) case, where $l=2$, and you're interpolating between the four possible binary inputs $(0,0),(0,1),(1,0),(1,1)$ as we saw in the previous example.

This is all you need to know about Multi-dimensional Lagrange Interpolation for Multilinear extensions. Hope this article was helpful. The next article will be a full guide on the sumcheck protocol. We’ll be applying everything we’ve learned so far.