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 $O(2^m)$ field operations and only $O(m)$ space. This improves on a previous algorithm due to Vu et al. (SP, 2013), which similarly uses $O(2^m)$ field operations but requires $O(2^m)$ space. Furthermore, the number of field additions in our algorithm is about half of that in Vu et al.'s algorithm, whereas the number of multiplications is the same up to small additive terms.