
























Abstract: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.
| Subjects: | Combinatorics (math.CO); Machine Learning (cs.LG); Probability (math.PR) |
| Cite as: | arXiv:2605.22666 [math.CO] |
| (or arXiv:2605.22666v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.22666 arXiv-issued DOI via DataCite (pending registration) |
From: Balazs Szegedy [view email]
[v1]
Thu, 21 May 2026 16:08:52 UTC (16 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。