Paper 2024/1103

A Note on Efficient Computation of the Multilinear Extension

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.