🔢 mathematics

Holographic functions and neural networks

This paper establishes the quantitative equivalence of three distinct notions of bounded complexity for fuzzy Boolean functions: a holographic sampling property, a structural approximation by low-degree polynomials, and a computational representation by bounded neural networks.

Original authors: Balazs Szegedy

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Balazs Szegedy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, high-resolution digital image. It's so big that looking at every single pixel would take forever. Now, imagine you want to know if the image contains a cat.

This paper asks a fundamental question: How much of the image do you actually need to look at to figure out what's in it?

The author, Balázs Szegedy, explores a special kind of "fuzzy" decision-making. Instead of a simple "yes" or "no," the function gives a probability (a number between 0 and 1) indicating how likely it is that the input has a certain property. The paper proves that three seemingly different ways of describing "simple" or "manageable" complexity are actually the same thing, just viewed through different lenses.

Here are the three lenses, explained with analogies:

1. The Holographic Property (The "Magic Window")

The Concept: A function is "holographic" if you can guess its answer by looking at just a tiny, random handful of pieces of the input.
The Analogy: Think of a hologram. If you break a holographic sticker into a million tiny shards, each shard still contains the information to reconstruct the whole image (though it might be a bit blurry).
In this paper, a "holographic function" is like that sticker. Even if the input is a massive string of 1,000,000 bits (like a giant image), you don't need to read the whole thing. You just need to randomly pick, say, 50 bits. Based on those 50 bits, you can predict the answer with high accuracy. The information isn't stored in one specific spot; it's distributed everywhere, like a hologram.

2. The Polynomial Property (The "Simple Recipe")

The Concept: A function is "polynomial" if it can be approximated by a mathematical recipe that mixes a few simple averages together.
The Analogy: Imagine you are trying to describe the taste of a complex soup. Instead of listing every single ingredient and its exact chemical structure, you realize the taste is just a simple mix of three things: "how salty it is," "how sour it is," and "how hot it is."
The paper shows that if a function is holographic (you can guess it from a few samples), it can also be written as a simple math formula. This formula takes a few "averages" of the input (like the average saltiness) and mixes them together using a standard polynomial (like $Salt^2 + Sour \times Hot$ ). It proves that complex-looking behaviors can often be boiled down to a few simple, linear ingredients mixed together.

3. The Neural Network Property (The "Factory Assembly Line")

The Concept: A function is "neural network" representable if it can be built by a small, simple factory of logic gates.
The Analogy: Think of a factory assembly line. Raw materials (the input bits) come in. They pass through a series of stations. At each station, a worker does a simple job: they take a weighted average of what they received, add a little bias, and then pass it through a "filter" (an activation function) that decides how much of it to pass on.
The paper defines a "bounded" network as one that doesn't have an infinite number of workers or infinitely complex tools. It has a limited number of stations, and each station only uses a limited amount of "strength" (weights) to process the data. The paper proves that if a function is holographic or polynomial, it can be built by such a simple factory.

The Big Discovery: They Are All the Same

The main result of the paper is a "Rosetta Stone" for complexity. It proves that these three ideas are qualitatively equivalent.

If you can guess the answer by looking at a few random bits (Holographic),
Then you can write the answer as a simple math recipe mixing a few averages (Polynomial),
And you can also build a simple factory to calculate the answer (Neural Network).

The paper shows that you can translate between these three languages without losing the essence of the problem. If a function is "simple" in the holographic sense, it is automatically "simple" in the neural network sense, and vice versa.

Why This Matters (According to the Paper)

The author suggests that this explains why neural networks are so good at machine learning. In many real-world problems (like recognizing images), the information is "holographically distributed." The answer doesn't depend on one specific pixel; it depends on the general pattern spread across the whole image.

Because the information is distributed this way, it naturally fits into a "simple recipe" (polynomial) and can be easily built by a "simple factory" (neural network). The paper provides a rigorous mathematical proof that these concepts of "distributed information," "simple math," and "neural networks" are all describing the same underlying reality.

In short: The paper proves that if a problem is solvable by looking at just a few random clues, it is also solvable by a simple math formula and a simple neural network. They are just different ways of saying the same thing.

Technical Summary: Holographic Functions and Neural Networks

Problem Statement
The paper addresses the question of whether a mathematically robust complexity theory exists for "fuzzy Boolean functions" (maps $f: \{0, 1\}^n \to [0, 1]$ ) that reflects their representability or approximability by neural networks of bounded complexity. While universal approximation theorems and specific quantitative results exist in the literature, this work seeks a dimension-independent structural viewpoint. The central motivation is the observation that in many machine learning contexts, the information determining $f(x)$ is "holographically distributed" among the input bits; that is, $f(x)$ can be estimated with high probability and small error from a bounded number of randomly sampled coordinates, provided the sampling locations are known.

Methodology
The author establishes the equivalence of three distinct notions of bounded complexity for fuzzy Boolean functions. The methodology relies on proving cyclic qualitative implications between these properties, where "qualitative equivalence" (Definition 1.3) means that one property implies another with dimension-independent control over complexity and accuracy parameters.

The three properties compared are:

The Holographic Property: A sampling property where $f(x)$ is recoverable from a bounded number of randomly chosen coordinates.
The Polynomial Property: A structural property where $f$ is uniformly close to a bounded-degree polynomial in a bounded number of bounded linear coordinate forms (with bounded $\ell_1$ -norms).
The Bounded Neural-Network Property: A computational property where $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.

The proofs utilize tools from extremal combinatorics and probability:

From Holography to Polynomials: The proof employs a variant of the weak hypergraph regularity lemma (specifically a "box regularity lemma," Theorem 3.2). By averaging the holographic test functions, the author constructs an approximation of $f$ and then uses the regularity lemma to approximate the resulting coefficient arrays by step functions on a bounded partition. This transforms the sampling-based definition into a polynomial structure.
From Polynomials to Neural Networks: This direction is an algebraic realization result. The author demonstrates that bounded-degree polynomials in bounded linear forms can be exactly computed by bounded-size neural networks using iterative multiplication modules (Lemma 4.1) and clipped activation functions.
From Neural Networks to Holography: This direction uses an inductive argument over the computational graph of the network. The core lemma (Lemma 5.1) states that a bounded affine average of bounded quantities can be estimated from a bounded number of random samples. By propagating this sampling capability through the network layers, the author shows that the output of a bounded network can be estimated from a bounded sample of inputs.

Key Contributions and Results
The main result is Theorem 1.8, which establishes that the holographic, polynomial, and bounded neural-network properties are qualitatively equivalent. Specifically:

(a) Every $(k, \varepsilon)$ -holographic function has the $(K_1, 3\varepsilon)$ -polynomial property.
(b) Every function with the $(K, \varepsilon)$ -polynomial property has the $(K_2, \varepsilon)$ -bounded neural-network property.
(c) Every function with the $(K, \varepsilon)$ -bounded neural-network property is $(K_3, 3\varepsilon)$ -holographic.

The paper also provides:

Example 2.1 & 2.2: Demonstrations that functions of weighted coordinate averages and small juntas satisfy the holographic property.
Example 2.3: An obstruction showing that the parity function is not holographic with bounded sample complexity, illustrating the limitations of the class.
Proposition 7.2: A proof that the definition of holography allowing distinct sampling measures for each query position is qualitatively equivalent to the stricter version requiring a single identical sampling measure, provided the sample size is increased logarithmically.

Significance and Claims
The paper claims to isolate a specific regime where the relationship between abstract complexity notions and neural network representability is rigorous and conceptually transparent. By proving the equivalence of these three properties, the work suggests that characteristic features of neural networks—specifically, large weighted averages followed by local nonlinearities—can emerge naturally from abstract complexity notions like holographic recoverability.

The author notes that the implication from holography to polynomial structure relies on a regularity lemma and thus has relatively poor quantitative dependence on parameters in general. However, the other two implications have more elementary dependencies once the dimension of the polynomial representation or network complexity is fixed. The work does not propose new applications or experimental proposals but rather offers a theoretical framework connecting sampling properties, polynomial approximation, and neural network architecture for fuzzy Boolean functions.

1. The Holographic Property (The "Magic Window")

2. The Polynomial Property (The "Simple Recipe")

3. The Neural Network Property (The "Factory Assembly Line")

The Big Discovery: They Are All the Same

Why This Matters (According to the Paper)

More like this