Overview

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.

Formulation :

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:

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

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.

How It Uses Lagrange Concepts

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

• Generalization: The multilinear extension extends the concept of interpolation from one dimension to multiple dimensions. The basis polynomials in both cases are structured to ensure that the extended function preserves the behavior of the original function at specified points (the vertices).

What is the Boolean Hypercube ?

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.

               000---------001
              / |          / |
             /  |         /  |    3-Dimensional Boolean Hypercube:
            010--------011   |    {000,001,010,011,100,101,110,111}
            |   |        |   |
            |   100------|-101
            |  /         |  /
            | /          | /
            110--------111
  

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.

Derivation of Multilinear Extension

• 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})$

    • $v_1 = ( 𝑥_{𝑣 _1} , 𝑦_{𝑣 _1})$

    • $v_2 = ( 𝑥_{𝑣 _2} , 𝑦_{𝑣 _2})$

    • $v_3 = ( 𝑥_{𝑣_3} , 𝑦_{𝑣 _3})$

  • Lagrange Basis Functions:

    • To construct the MLE, we first need to define the Lagrange basis functions. These functions will ensure that the MLE passes through the vertex values of $f$.

    • The Lagrange basis functions for the vertices $𝑣_0, 𝑣_1,$, $v_2$ and $v_3$ ​ are:

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 $𝑥_1 ​ = x_{v_1}$ or $𝑥_2 ​ = y_{v_1}$

• $L_1(x_1,x_2)$ is 1 when $𝑥_1 ​ = x_{v_1}$ ​and $𝑥_2 ​ = y_{v_0}$, and 0 when either $𝑥_1 ​ = x_{v_0}$ or $𝑥_2 ​ = y_{v_1}$

• $L_2(x_1,x_2)$ is 1 when $𝑥_1 ​ = x_{v_0}$ ​and $𝑥_2 ​ = y_{v_1}$, and 0 when either $𝑥_1 ​ = x_{v_1}$ or $𝑥_2 ​ = y_{v_0}$

• $L_3(x_1,x_2)$ is 1 when $𝑥_1 ​ = x_{v_1}$ ​and $𝑥_2 ​ = y_{v_1}$, and 0 when either $𝑥_1 ​ = x_{v_0}$ or $𝑥_2 ​ = y_{v_0}$

• Formulating the Multilinear Extension:

  • Now, we can express the multilinear extension $\tilde{f}(x,y)$ using the function values at the vertices and the Lagrange basis functions:

• Final Formula (Simplified):

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

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

Example

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

The MLE of the bivariate function will look like this:

which we can simplify it to:

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:

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.

Conclusion

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.