Holographic functions and neural networks

Balazs Szegedy

arxiv: 2605.22666 · v1 · pith:35SMIH5Wnew · submitted 2026-05-21 · 🧮 math.CO · cs.LG· math.PR

Holographic functions and neural networks

Balazs Szegedy This is my paper

Pith reviewed 2026-05-22 04:04 UTC · model grok-4.3

classification 🧮 math.CO cs.LGmath.PR

keywords fuzzy Boolean functionsholographic propertyneural network approximationpolynomial approximationhypergraph regularitybounded complexitysampling property

0 comments

The pith

Bounded complexity for fuzzy Boolean functions is equivalent across holographic sampling, polynomial structure in linear forms, and neural network approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that three different ways of saying a fuzzy Boolean function has bounded complexity are equivalent, up to changes in the specific numerical bounds. The first requires that the function value at any point can be recovered with high probability by looking at only a bounded number of randomly sampled coordinates. The second requires the function to be close to a low-degree polynomial that depends on only a bounded number of linear combinations of the input coordinates. The third requires the function to be close to the output of a neural network that has a bounded number of hidden neurons, bounded-Lipschitz activation functions, and bounded incoming weights. A reader interested in the interplay between sampling, algebra, and computation would care because the result lets one move results and techniques freely between these three viewpoints.

Core claim

For a fuzzy Boolean function f mapping the hypercube to the unit interval, the holographic property, the property of being uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms, and the property of being uniformly close to the output of a neural network with bounded non-input neurons, bounded Lipschitz activations, and bounded incoming weights are equivalent up to quantitative changes of the parameters. The direction from the holographic property to the polynomial structure is proved using a variant of a weak hypergraph regularity lemma.

What carries the argument

The equivalence (up to parameter changes) between the holographic sampling property, approximation by bounded-degree polynomials in linear coordinate forms, and approximation by bounded neural networks with Lipschitz activations.

If this is right

A function recoverable from few random coordinates is also approximable by a small neural network with Lipschitz activations.
Any function approximable by such a neural network is recoverable from few random coordinates.
The polynomial representation in linear forms acts as a structural bridge that transfers bounds between the sampling and computational views.
Quantitative changes in the bounds allow direct comparison of complexity measures across the three definitions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same equivalence might be used to derive new sampling-based learning guarantees for functions that admit small neural representations.
Similar equivalences could be investigated for functions on larger alphabets or for higher-order hypergraph versions of the regularity step.
The polynomial view may connect to existing Fourier-analytic or influence-based notions of complexity without additional assumptions.

Load-bearing premise

The step from the holographic property to polynomial structure holds only if a suitable variant of the weak hypergraph regularity lemma supplies the needed quantitative bounds.

What would settle it

A concrete fuzzy Boolean function that satisfies the holographic sampling property with small parameters yet stays far from every bounded-degree polynomial in any bounded collection of linear forms would show the claimed equivalence fails.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Szegedy shows holographic sampling, low-degree polynomials in linear forms, and bounded neural nets are equivalent for fuzzy Boolean functions, with the key step using a weak hypergraph regularity variant.

read the letter

The main point to know is that this paper proves an equivalence between three complexity notions for fuzzy Boolean functions: a holographic sampling property where the function value is recoverable from few random coordinates, uniform approximation by a low-degree polynomial in few bounded linear forms, and approximation by a small neural network with bounded weights and Lipschitz activations. The paper does a solid job defining these properties independently and showing they are equivalent up to changes in the parameters. The new aspect is the specific three-way link for these particular definitions on [0,1]-valued functions on the cube. It connects ideas from sampling, algebraic combinatorics, and neural network theory in a direct way. What works is the use of a variant of weak hypergraph regularity to handle the direction from the sampling property to the polynomial structure. This seems like an appropriate tool for the job and avoids obvious circularity since the properties are defined separately. The soft spot is in the details of that regularity variant. The abstract says it is used for the implication, but to confirm the quantitative equivalence, one needs to see that the degree and number of forms depend only on the holographic parameters without bad blow-ups in the error terms. If the variant is too weak or requires extra assumptions, that direction might not go through as cleanly as stated. The other directions look more straightforward. This paper is for people in extremal combinatorics and theoretical machine learning who want to see regularity methods applied to function approximation and neural net complexity. A reader with background in hypergraph regularity will get the most out of the proof ideas. It shows honest engagement with the literature by building on known regularity tools rather than reinventing them. The work deserves a serious referee to examine the proof of the main implication and the resulting constants. I recommend sending it to peer review. The claim is interesting enough and grounded enough to justify the time for detailed comments.

Referee Report

1 major / 2 minor

Summary. The paper defines three notions of bounded complexity for fuzzy Boolean functions f:{0,1}^n → [0,1]: the holographic property (recovering f(x) up to small error from a bounded number of random coordinates with high probability), uniform approximation by a bounded-degree polynomial in a bounded number of bounded linear forms, and uniform approximation by the output of a neural network with bounded non-input neurons, bounded Lipschitz activations, and bounded incoming weights. It proves these three properties are equivalent up to quantitative changes in the parameters, with the direction from holography to polynomial structure relying on a variant of the weak hypergraph regularity lemma.

Significance. If the quantitative equivalences hold, the result would connect sampling-based, algebraic, and computational notions of simplicity for functions on the hypercube, with potential relevance to Boolean analysis, property testing, and neural network approximation theory. The manuscript supplies a proof rather than an empirical claim, which strengthens the contribution; however, the strength of the central equivalence rests on the correctness and parameter control of the invoked regularity variant.

major comments (1)

[Section 3 (proof of the holography-to-polynomial implication)] The proof that the holographic property implies the polynomial-structure property (the direction stated to use a variant of weak hypergraph regularity) requires an explicit statement of the variant lemma, including the precise dependence of the degree and number-of-forms bounds on the holographic parameters ε, k, and δ. Without this, it is impossible to verify that the quantitative equivalence claimed in the main theorem holds without uncontrolled blow-up in the parameters.

minor comments (2)

[Section 2] Notation for the linear forms and the precise definition of 'bounded linear coordinate forms' should be introduced earlier and used consistently across the three properties.
[Abstract] The abstract mentions 'quantitative changes of the parameters' but does not indicate whether the changes are polynomial or exponential; a brief remark on the nature of the quantitative dependence would help readers assess applicability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the need to make the quantitative aspects of the holography-to-polynomial implication fully explicit. We address the major comment below and will revise the manuscript to incorporate the requested clarification.

read point-by-point responses

Referee: [Section 3 (proof of the holography-to-polynomial implication)] The proof that the holographic property implies the polynomial-structure property (the direction stated to use a variant of weak hypergraph regularity) requires an explicit statement of the variant lemma, including the precise dependence of the degree and number-of-forms bounds on the holographic parameters ε, k, and δ. Without this, it is impossible to verify that the quantitative equivalence claimed in the main theorem holds without uncontrolled blow-up in the parameters.

Authors: We agree that an explicit statement of the variant lemma is required to allow verification of the claimed quantitative equivalence. In the revised manuscript we will insert, at the beginning of Section 3, a self-contained statement of the variant of the weak hypergraph regularity lemma that is invoked. The statement will record the precise functional dependence of the resulting degree bound and the number of linear forms on the holographic parameters ε, k, and δ. The subsequent proof will be updated to cite this lemma directly, confirming that the parameter changes remain controlled and that no uncontrolled blow-up occurs. revision: yes

Circularity Check

0 steps flagged

No circularity: equivalence proof between independently defined complexity measures

full rationale

The paper defines three distinct notions of bounded complexity for fuzzy Boolean functions on the cube: (1) the holographic sampling property (recovering f(x) from few random coordinates), (2) uniform approximation by a bounded-degree polynomial in boundedly many bounded linear forms, and (3) approximation by a neural network with bounded neurons, Lipschitz activations, and weights. It then proves logical equivalence (up to quantitative parameter changes) among these independently stated properties. The one direction that invokes a variant of weak hypergraph regularity is an external analytic tool applied to the sampling assumption; it does not reduce any claimed result to a fitted parameter, self-definition, or prior self-citation that itself depends on the target equivalence. No equation or claim in the derivation is forced by construction from its own inputs, and the central theorem remains a non-tautological implication between separate definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central proof direction relies on an external combinatorial tool whose details are not supplied in the abstract.

axioms (1)

domain assumption A variant of the weak hypergraph regularity lemma holds and can be applied to the sampling property.
Invoked explicitly for the holography-to-polynomial implication.

pith-pipeline@v0.9.0 · 5685 in / 1060 out tokens · 31295 ms · 2026-05-22T04:04:21.170254+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that these three properties are equivalent up to quantitative changes of the parameters.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Cybenko,Approximation by superpositions of a sigmoidal function, Math

G. Cybenko,Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems2(1989), no. 4, 303–314

work page 1989
[2]

Frieze and R

A. Frieze and R. Kannan,Quick approximation to matrices and applications, Combinatorica19(1999), 175–220

work page 1999
[3]

W. T. Gowers,Hypergraph regularity and the multidimensional Szemer´ edi theorem, Ann. of Math.166(2007), 897–946

work page 2007
[4]

Hornik,Approximation capabilities of multilayer feedforward networks, Neural Networks4(1991), no

K. Hornik,Approximation capabilities of multilayer feedforward networks, Neural Networks4(1991), no. 2, 251–257

work page 1991
[5]

Kohayakawa, B

Y. Kohayakawa, B. Nagle, V. R¨ odl, M. Schacht and J. Skokan,The hypergraph regularity method and its appli- cations, Proc. Natl. Acad. Sci. USA102(2005), no. 23, 8109–8113

work page 2005
[6]

Pinkus,Approximation theory of the MLP model in neural networks, Acta Numerica8(1999), 143–195

A. Pinkus,Approximation theory of the MLP model in neural networks, Acta Numerica8(1999), 143–195

work page 1999
[7]

Szemer´ edi,Regular partitions of graphs, inProbl` emes Combinatoires et Th´ eorie des Graphes, Colloques Internationaux CNRS, No

E. Szemer´ edi,Regular partitions of graphs, inProbl` emes Combinatoires et Th´ eorie des Graphes, Colloques Internationaux CNRS, No. 260, CNRS, Paris, 1978, pp. 399–401

work page 1978
[8]

Tao,A variant of the hypergraph removal lemma, J

T. Tao,A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A113(2006), 1257–1280

work page 2006
[9]

Yarotsky,Error bounds for approximations with deep ReLU networks, Neural Networks94(2017), 103–114

D. Yarotsky,Error bounds for approximations with deep ReLU networks, Neural Networks94(2017), 103–114. R´enyi Institute of Mathematics, Budapest, Hungary Email address:szegedyb@gmail.com 15

work page 2017

[1] [1]

Cybenko,Approximation by superpositions of a sigmoidal function, Math

G. Cybenko,Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems2(1989), no. 4, 303–314

work page 1989

[2] [2]

Frieze and R

A. Frieze and R. Kannan,Quick approximation to matrices and applications, Combinatorica19(1999), 175–220

work page 1999

[3] [3]

W. T. Gowers,Hypergraph regularity and the multidimensional Szemer´ edi theorem, Ann. of Math.166(2007), 897–946

work page 2007

[4] [4]

Hornik,Approximation capabilities of multilayer feedforward networks, Neural Networks4(1991), no

K. Hornik,Approximation capabilities of multilayer feedforward networks, Neural Networks4(1991), no. 2, 251–257

work page 1991

[5] [5]

Kohayakawa, B

Y. Kohayakawa, B. Nagle, V. R¨ odl, M. Schacht and J. Skokan,The hypergraph regularity method and its appli- cations, Proc. Natl. Acad. Sci. USA102(2005), no. 23, 8109–8113

work page 2005

[6] [6]

Pinkus,Approximation theory of the MLP model in neural networks, Acta Numerica8(1999), 143–195

A. Pinkus,Approximation theory of the MLP model in neural networks, Acta Numerica8(1999), 143–195

work page 1999

[7] [7]

Szemer´ edi,Regular partitions of graphs, inProbl` emes Combinatoires et Th´ eorie des Graphes, Colloques Internationaux CNRS, No

E. Szemer´ edi,Regular partitions of graphs, inProbl` emes Combinatoires et Th´ eorie des Graphes, Colloques Internationaux CNRS, No. 260, CNRS, Paris, 1978, pp. 399–401

work page 1978

[8] [8]

Tao,A variant of the hypergraph removal lemma, J

T. Tao,A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A113(2006), 1257–1280

work page 2006

[9] [9]

Yarotsky,Error bounds for approximations with deep ReLU networks, Neural Networks94(2017), 103–114

D. Yarotsky,Error bounds for approximations with deep ReLU networks, Neural Networks94(2017), 103–114. R´enyi Institute of Mathematics, Budapest, Hungary Email address:szegedyb@gmail.com 15

work page 2017