Expand description
Reduction from the products over the sumcubes of a multilinear to a multilinear evaluation.
The reduction input is a multilinear $f(Z_0, \ldots, Z_{k-1}, X_0, \ldots, X_{n-1})$. The product polynomial is the multilinear
$$ p(X_0, \ldots, X_{n-1}) = \sum_{x \in B_n} \text{eq}(x ; X) \prod_{z \in B_k} f(z, x) $$
This protocol is a GKR-based protocol with $k$ sumcheck invocations. We define a sequence of multilinears $p_0, \ldots, p_k$, where $p_k = f$ and for all $i < k$:
$$ p_i(Z_0, \ldots, Z_{i-1}, X_0, \ldots, X_{n-1}) = \sum_{x \in B_n} \sum_{z \in B_i} \text{eq}(x ; X) \text{eq}(z ; Z) p_{i+1}(z, 0, x) p_{i+1}(z, 1, x) $$
Re-exports§
pub use crate::MultilinearEvalClaim;