Holographic functions and neural networks

Balázs Szegedy’s paper introduces a dimension-independent complexity theory for fuzzy Boolean functions f:{0,1}^n→[0,1] and proves an equivalence between three notions: holographic recoverability, low-dimensional polynomial structure, and bounded neural-network representability. The holographic property says that f(x) can be reconstructed up to small error from k randomly sampled coordinates, with test functions allowed to depend on the sampled locations; the structural counterpart is approximation by a degree-at-most-K polynomial in at most K bounded linear forms with ℓ1-norm-bounded coefficients; the computational counterpart is approximation by a bounded-Lipschitz directed acyclic network with at most K non-input neurons and bounded incoming affine norms. The main theorem shows these properties are qualitatively equivalent, with explicit parameter blowups: holography implies polynomial structure via a weak hypergraph-regularity, or box-regularity, lemma; polynomial structure implies neural realizability by an exact multiplication gadget built from clipped squaring χ(t)=min(1,max(0,t)) and ψ(t)=χ(t)^2; and bounded networks imply holography by inductively sampling bounded affine forms using Hoeffding’s inequality. The paper also proves that allowing different sampling measures per query is qualitatively equivalent to using one common measure, with a sample overhead O(k log(1/ε))). Novelty lies in identifying holography as the bridge between distributed redundancy in high-dimensional data and bounded neural computation.