Multilinear Extension (MLE) under evaluation form and coefficient form includes the core operations of point evaluation, addition, and multiplication. Through formal derivation and formulaic description, it demonstrates efficient computation in different representations, particularly pointwise operations on the Boolean hypercube {0,1}v. This framework provides a solid mathematical foundation and algorithmic support for the multivariate sumcheck protocol and its applications in zero-knowledge proofs (zkSNARKs).
In the evaluation form, a multilinear extension \( \tilde{f} : \mathbb{F}^n \rightarrow \mathbb{F} \) is determined by its values on the Boolean hypercube \( \{0, 1\}^n \). By multilinearity, one can evaluate \( f \) at any point \( r \in \mathbb{F} \) without explicitly converting back to the coefficient form. This method relies on a recursive interpolation formula, which progressively reduces the dimensionality of the constraints of the high-dimensional function.
Let the evaluation vector of \( \tilde{f} \) be
\[ E = (f(x_1, \ldots, x_n))_{(x_1, \ldots, x_n) \in \{0, 1\}^n} \]
To compute \( \tilde{f}(r, x_2, \ldots, x_n) \), multilinearity gives
\[ \tilde{f}(r, x_2, \ldots, x_n) = (1 - r) \tilde{f}(0, x_2, \ldots, x_n) + r \tilde{f}(1, x_2, \ldots, x_n). \]
The corresponding algorithmic operation is
\[ E[t] = E[t] + r \cdot \left[ E[t + 2^{r-1}] - E[t] \right], \quad t = 0, 1, \ldots, 2^{r-1} - 1. \]
Here, \( E \) represents the \( (n - 1) \)-variable evaluation vector after setting \( x_1 = r \).
Both the time and space complexities are \( O(2^n) \).
In the coefficient form, a multilinear extension \( \tilde{f} \) is derived from the function \( f: \{0, 1\}^n \rightarrow \mathbb{F} \) on the Boolean hypercube, expanded with the corresponding Lagrange basis functions. Its advantage is that one can directly substitute any point \( r \in \mathbb{F}^n \) to obtain the evaluation result without relying on recursive interpolation.
The coefficient form of \( \tilde{f} \) is
\[ \tilde{f}(x_1, \ldots, x_n) = \sum_{w \in \{0,1\}^n} f(w) \chi_w(x_1, \ldots, x_n), \]
where
\[ \chi_w(x_1, \ldots, x_n) = \prod_{i=1}^n \left( (1 - w_i)(1 - x_i) + w_i x_i \right) \]
is the Lagrange basis function.
At a specific point \( r = (r_1, \ldots, r_n) \in \mathbb{F}^n \), the evaluation formula is
\[ \tilde{f}(r) = \sum_{w \in \{0,1\}^n} f(w) \chi_w(r). \]
This corresponds to directly substituting \( r \) in the coefficient form.
In multivariate polynomial systems, the operation MLE × MLE is widely used in zkSNARK protocols based on the multivariate sumcheck. Let \( f, g \) be two multilinear extension functions defined on the Boolean hypercube \( \{0, 1\}^v \) (i.e., each variable is linear). They can be represented by their value vectors over all \( 2^v \) points, which is the evaluation form. Using this form, one can efficiently compute \( f(r_1, \ldots, r_v) \cdot g(r_1, \ldots, r_v) \), i.e., directly multiply their values at a given point.
When multiplying two MLEs, if their current evaluation vectors are not of sufficient length (e.g., the degree has not reached the target \( d \)), they must be padded and extended to length \( d \). This is because multiplication increases the degree (up to doubling it), and maintaining a length-\( d \) vector ensures correctness for subsequent IFFT or Lagrange interpolation operations. The process is similar to handling univariate polynomials in FFT: perform pointwise multiplication in the evaluation domain after FFT, then recover to the coefficient domain via IFFT. For multivariate MLEs, pointwise multiplication follows the same principle but is carried out on the high-dimensional Boolean hypercube.
Let \( f, g: \{0, 1\}^v \to \mathbb{F} \) be two multilinear extension functions. Their evaluation forms are
\[ f = (f(w))_{w \in \{0,1\}^v} \quad g = (g(w))_{w \in \{0,1\}^v} \]
Then, at a point \( r = (r_1, \ldots, r_v) \in \mathbb{F}^v \), the multiplication is
\[ (f \cdot g)(r) = f(r) \cdot g(r). \]
In the coefficient form, we have
\[ f(x_1, \ldots, x_v) = \sum_{w \in \{0,1\}^v} f(w) \chi_w(x_1, \ldots, x_v), \quad g(x_1, \ldots, x_v) = \sum_{u \in \{0,1\}^v} g(u) \chi_u(x_1, \ldots, x_v), \]
where the basis functions are
\[ \chi_w(x_1, \ldots, x_v) = \prod_{i=1}^v \left( (1 - w_i)(1 - x_i) + w_i x_i \right). \]
Thus, the multiplication result is
\[ (f \cdot g)(x_1, \ldots, x_v) = \sum_{w \in \{0,1\}^v} \sum_{u \in \{0,1\}^v} f(w) g(u) \chi_w(x_1, \ldots, x_v) \chi_u(x_1, \ldots, x_v). \]
In the evaluation form, this is equivalent to the Hadamard product:
\[ h = f \odot g, \quad \text{where } h(w) = f(w) \cdot g(w), \quad \forall w \in \{0,1\}^v. \]
In the multivariate case, polynomial addition is essentially pointwise addition:
Given two polynomials \( f, g \colon \{0, 1\}^v \to \mathbb{F} \), their sum at any point \( w \in \{0, 1\}^v \) is defined as \((f + g)(w) = f(w) + g(w)\). In different representations, this operation is expressed as:
· In the coefficient form, the coefficients of the corresponding basis functions are added entrywise;
· In the evaluation form, the function values at corresponding points are added entrywise.
This structure ensures that addition can be performed in linear time in both forms, with computational and storage costs of \( O(2^v) \).
· For \( f, g \colon \{0, 1\}^v \to \mathbb{F} \), polynomial addition is defined as
\[ (f + g)(x_1, \ldots, x_v) = f(x_1, \ldots, x_v) + g(x_1, \ldots, x_v). \]
· Coefficient form: If
\[ f(x) = \sum_{w \in \{0,1\}^v} a_w \chi_w(x), \quad g(x) = \sum_{w \in \{0,1\}^v} b_w \chi_w(x), \] then \[ (f + g)(x) = \sum_{w \in \{0,1\}^v} (a_w + b_w) \chi_w(x). \]
· Evaluation form: If
\[ f = (f(w))_{w \in \{0,1\}^v}, \quad g = (g(w))_{w \in \{0,1\}^v} \] then \[ h = f + g, \quad \text{where } h(w) = f(w) + g(w), \quad \forall w \in \{0,1\}^v. \]
By comparing the evaluation form and the coefficient form, we have illustrated the basic computational mechanisms of multilinear extensions over high-dimensional Boolean hypercubes. In the evaluation form, recursive dimensional reduction allows efficient point evaluation, while multiplication and addition correspond to the Hadamard product and vector addition. In the coefficient form, MLEs are expanded with Lagrange basis functions, with evaluation and algebraic operations reduced to entrywise coefficient manipulation. Both representations are equivalent in expressive power but have different advantages: evaluation form is better suited for numerical computation and parallelization, while coefficient form facilitates algebraic derivation and protocol design. Overall, this provides a unified theoretical framework and computational toolkit for polynomial operations in the multivariate sumcheck protocol.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
Explore the ZKM Docs
Start building with ZKM GitHub
Follow ZKM on X
Multilinear Extension (MLE) under evaluation form and coefficient form includes the core operations of point evaluation, addition, and multiplication. Through formal derivation and formulaic description, it demonstrates efficient computation in different representations, particularly pointwise operations on the Boolean hypercube {0,1}v. This framework provides a solid mathematical foundation and algorithmic support for the multivariate sumcheck protocol and its applications in zero-knowledge proofs (zkSNARKs).
In the evaluation form, a multilinear extension \( \tilde{f} : \mathbb{F}^n \rightarrow \mathbb{F} \) is determined by its values on the Boolean hypercube \( \{0, 1\}^n \). By multilinearity, one can evaluate \( f \) at any point \( r \in \mathbb{F} \) without explicitly converting back to the coefficient form. This method relies on a recursive interpolation formula, which progressively reduces the dimensionality of the constraints of the high-dimensional function.
Let the evaluation vector of \( \tilde{f} \) be
\[ E = (f(x_1, \ldots, x_n))_{(x_1, \ldots, x_n) \in \{0, 1\}^n} \]
To compute \( \tilde{f}(r, x_2, \ldots, x_n) \), multilinearity gives
\[ \tilde{f}(r, x_2, \ldots, x_n) = (1 - r) \tilde{f}(0, x_2, \ldots, x_n) + r \tilde{f}(1, x_2, \ldots, x_n). \]
The corresponding algorithmic operation is
\[ E[t] = E[t] + r \cdot \left[ E[t + 2^{r-1}] - E[t] \right], \quad t = 0, 1, \ldots, 2^{r-1} - 1. \]
Here, \( E \) represents the \( (n - 1) \)-variable evaluation vector after setting \( x_1 = r \).
Both the time and space complexities are \( O(2^n) \).
In the coefficient form, a multilinear extension \( \tilde{f} \) is derived from the function \( f: \{0, 1\}^n \rightarrow \mathbb{F} \) on the Boolean hypercube, expanded with the corresponding Lagrange basis functions. Its advantage is that one can directly substitute any point \( r \in \mathbb{F}^n \) to obtain the evaluation result without relying on recursive interpolation.
The coefficient form of \( \tilde{f} \) is
\[ \tilde{f}(x_1, \ldots, x_n) = \sum_{w \in \{0,1\}^n} f(w) \chi_w(x_1, \ldots, x_n), \]
where
\[ \chi_w(x_1, \ldots, x_n) = \prod_{i=1}^n \left( (1 - w_i)(1 - x_i) + w_i x_i \right) \]
is the Lagrange basis function.
At a specific point \( r = (r_1, \ldots, r_n) \in \mathbb{F}^n \), the evaluation formula is
\[ \tilde{f}(r) = \sum_{w \in \{0,1\}^n} f(w) \chi_w(r). \]
This corresponds to directly substituting \( r \) in the coefficient form.
In multivariate polynomial systems, the operation MLE × MLE is widely used in zkSNARK protocols based on the multivariate sumcheck. Let \( f, g \) be two multilinear extension functions defined on the Boolean hypercube \( \{0, 1\}^v \) (i.e., each variable is linear). They can be represented by their value vectors over all \( 2^v \) points, which is the evaluation form. Using this form, one can efficiently compute \( f(r_1, \ldots, r_v) \cdot g(r_1, \ldots, r_v) \), i.e., directly multiply their values at a given point.
When multiplying two MLEs, if their current evaluation vectors are not of sufficient length (e.g., the degree has not reached the target \( d \)), they must be padded and extended to length \( d \). This is because multiplication increases the degree (up to doubling it), and maintaining a length-\( d \) vector ensures correctness for subsequent IFFT or Lagrange interpolation operations. The process is similar to handling univariate polynomials in FFT: perform pointwise multiplication in the evaluation domain after FFT, then recover to the coefficient domain via IFFT. For multivariate MLEs, pointwise multiplication follows the same principle but is carried out on the high-dimensional Boolean hypercube.
Let \( f, g: \{0, 1\}^v \to \mathbb{F} \) be two multilinear extension functions. Their evaluation forms are
\[ f = (f(w))_{w \in \{0,1\}^v} \quad g = (g(w))_{w \in \{0,1\}^v} \]
Then, at a point \( r = (r_1, \ldots, r_v) \in \mathbb{F}^v \), the multiplication is
\[ (f \cdot g)(r) = f(r) \cdot g(r). \]
In the coefficient form, we have
\[ f(x_1, \ldots, x_v) = \sum_{w \in \{0,1\}^v} f(w) \chi_w(x_1, \ldots, x_v), \quad g(x_1, \ldots, x_v) = \sum_{u \in \{0,1\}^v} g(u) \chi_u(x_1, \ldots, x_v), \]
where the basis functions are
\[ \chi_w(x_1, \ldots, x_v) = \prod_{i=1}^v \left( (1 - w_i)(1 - x_i) + w_i x_i \right). \]
Thus, the multiplication result is
\[ (f \cdot g)(x_1, \ldots, x_v) = \sum_{w \in \{0,1\}^v} \sum_{u \in \{0,1\}^v} f(w) g(u) \chi_w(x_1, \ldots, x_v) \chi_u(x_1, \ldots, x_v). \]
In the evaluation form, this is equivalent to the Hadamard product:
\[ h = f \odot g, \quad \text{where } h(w) = f(w) \cdot g(w), \quad \forall w \in \{0,1\}^v. \]
In the multivariate case, polynomial addition is essentially pointwise addition:
Given two polynomials \( f, g \colon \{0, 1\}^v \to \mathbb{F} \), their sum at any point \( w \in \{0, 1\}^v \) is defined as \((f + g)(w) = f(w) + g(w)\). In different representations, this operation is expressed as:
· In the coefficient form, the coefficients of the corresponding basis functions are added entrywise;
· In the evaluation form, the function values at corresponding points are added entrywise.
This structure ensures that addition can be performed in linear time in both forms, with computational and storage costs of \( O(2^v) \).
· For \( f, g \colon \{0, 1\}^v \to \mathbb{F} \), polynomial addition is defined as
\[ (f + g)(x_1, \ldots, x_v) = f(x_1, \ldots, x_v) + g(x_1, \ldots, x_v). \]
· Coefficient form: If
\[ f(x) = \sum_{w \in \{0,1\}^v} a_w \chi_w(x), \quad g(x) = \sum_{w \in \{0,1\}^v} b_w \chi_w(x), \] then \[ (f + g)(x) = \sum_{w \in \{0,1\}^v} (a_w + b_w) \chi_w(x). \]
· Evaluation form: If
\[ f = (f(w))_{w \in \{0,1\}^v}, \quad g = (g(w))_{w \in \{0,1\}^v} \] then \[ h = f + g, \quad \text{where } h(w) = f(w) + g(w), \quad \forall w \in \{0,1\}^v. \]
By comparing the evaluation form and the coefficient form, we have illustrated the basic computational mechanisms of multilinear extensions over high-dimensional Boolean hypercubes. In the evaluation form, recursive dimensional reduction allows efficient point evaluation, while multiplication and addition correspond to the Hadamard product and vector addition. In the coefficient form, MLEs are expanded with Lagrange basis functions, with evaluation and algebraic operations reduced to entrywise coefficient manipulation. Both representations are equivalent in expressive power but have different advantages: evaluation form is better suited for numerical computation and parallelization, while coefficient form facilitates algebraic derivation and protocol design. Overall, this provides a unified theoretical framework and computational toolkit for polynomial operations in the multivariate sumcheck protocol.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
Explore the ZKM Docs
Start building with ZKM GitHub
Follow ZKM on X
