Welcome to the resource topic for 2024/1103
Title:
A Note on Efficient Computation of the Multilinear Extension
Authors: Ron D. Rothblum
Abstract:The multilinear extension of an m-variate function f : \{0,1\}^m \to \mathbb{F}, relative to a finite field \mathbb{F}, is the unique multilinear polynomial \hat{f} : \mathbb{F}^m \to \mathbb{F} that agrees with f on inputs in \{0,1\}^m.
In this note we show how, given oracle access to f : \{0,1\}^m \to \mathbb{F} and a point z \in \mathbb{F}^m, to compute \hat{f}(z) using exactly 2^{m+1} multiplications, 2^m additions and O(m) additional operations. The amount of space used corresponds to O(m) field elements.
ePrint: https://eprint.iacr.org/2024/1103
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .