{"id":"arxiv/2605.22666","url":"https://arxiv.org/abs/2605.22666","tags":["math.CO","cs.LG","math.PR"],"score":0,"title":"Holographic functions and neural networks","domain":"math.CO","source":"arxiv","authors":["Balazs Szegedy"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-21","reactions":{}}