Holographic functions and neural networks
For theorists in machine learning and Boolean function analysis, this provides a unified framework linking seemingly distinct complexity measures, though the result is primarily theoretical and incremental in nature.
The paper proves that three notions of bounded complexity for fuzzy Boolean functions—holographic sampling property, approximation by bounded-degree polynomials in bounded linear forms, and approximation by neural networks with bounded size—are equivalent up to quantitative parameter changes. This establishes a formal connection between holographic data recovery, polynomial approximation, and neural network representation.
A fuzzy Boolean function is a map $f:\cube^n\to [0,1]$, where $n\in\mathbb N$. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value $f(x)$ can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of $x$. We call this the holographic property. The second is a structural property: $f$ is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational: $f$ is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.