In computer science and discrete mathematics, high-dimensional spaces are notoriously difficult to navigate. If a Boolean function takes $n$ input variables, its domain contains $2^n$ possible combinations, making exact learning or optimization exponentially expensive. However, many fundamental classes of functions—such as linear threshold functions (LTFs), submodular functions, and noise-stable concepts—possess a hidden structural simplicity: their behavior is almost entirely determined by a small subset of their inputs.
A function that depends on only $k$ of its $n$ variables is called a junta. When a complex, high-dimensional function can be closely approximated by a junta where $k \ll n$, the curse of dimensionality is broken. This article explores why these approximations work, how spectral concentration reveals them, and how they transform intractable computational problems into manageable ones.
The Core Intuition: Influence and the Fourier Spectrum
To understand why a high-dimensional function can be reduced to a few variables, we must look at how its variance is distributed. There are two primary lenses for this: variable influence and the Fourier spectrum.
The influence of a variable measures how likely a flip in that single coordinate is to change the function's output. Friedgut's Theorem establishes a foundational baseline: any Boolean function with low total influence can be approximated by a junta. However, general theorems often yield an exponential dependence on the influence parameter. To achieve practical algorithms, researchers look for tighter, polynomial relationships within specific function classes.
For instance, in Improved Approximation of Linear Threshold Functions, Ilias Diakonikolas et al. exponentially sharpened this relationship for LTFs. The authors demonstrated that an LTF can be decomposed into a set of high-weight variables and a regular remainder where no single weight dominates. This structural decomposition proves that LTFs can be approximated by juntas with a polynomial rather than exponential dependence on total influence, as further detailed by the authors in Improved Approximation of Linear Threshold Functions.
The second lens is spectral. Every Boolean function can be uniquely expressed as a polynomial via its Fourier expansion, where the coefficients represent the weight of interactions between subsets of variables. If a function's "Fourier energy" is concentrated on low-degree coefficients—meaning complex, high-order interactions contribute negligible variance—the function is structurally simple. As highlighted in Open Problem: Meeting Times for Learning Random Automata by Benjamin Fish et al., focusing on these significant spectral components is the key to making high-dimensional learning computationally feasible.
Why Structural Properties Force Low Dimensionality
Why do real-world function classes exhibit this convenient spectral concentration? The answer lies in their inherent mathematical constraints, such as submodularity or noise stability.
Submodularity and Diminishing Returns
Submodular functions model the principle of diminishing returns. Despite their combinatorial complexity, they are spectrally sparse. In Learning Coverage Functions and Private Release of Marginals, Vitaly Feldman et al. showed that coverage functions (a major subclass of submodularity) have a small spectral $\ell_1$-norm. This concentration allows them to be effectively approximated by juntas depending on a logarithmic number of variables.
Furthermore, Vitaly Feldman et al. in Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees proved that submodular functions can be closely approximated by low-depth decision trees, which are spectrally simple and correspond to low-degree polynomials. By applying a switching lemma to discrete function classes, Sofya Raskhodnikova et al. in Learning pseudo-Boolean k-DNF and Submodular Functions proved that submodular functions with small integer ranges have their variance captured almost entirely by low-degree Fourier coefficients. This was tightened by Vitaly Feldman et al. in Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions, establishing that their Fourier weight concentrates at degrees significantly lower than previously assumed.
Noise Stability and Global Constraints
Another powerful driver of low dimensionality is noise stability. If a function's output rarely changes when its inputs are subjected to slight random jitter, it cannot depend on complex, fragile combinations of many variables. In On Robust Concepts and Small Neural Nets, Amit Deshpande et al. proved that noise-stable Boolean functions reduce to low-dimensional juntas without significant loss of accuracy, explaining why they can be efficiently approximated by shallow, small-weight neural networks.
Similarly, global algebraic or logical constraints can force local coordinate dependence. In AND testing and robust judgement aggregation, Noam Lifshitz et al. used junta theorems to show that functions satisfying specific logical constraints effectively depend on a constant number of variables. This phenomenon extends to constrained domains; for instance, Yuval Filmus et al. in Invariance Principle on the Slice demonstrated that functions on a slice (where coordinates are dependent) that approximate low-degree polynomials are essentially determined by a small number of coordinates. In Approximate polymorphisms, Gilad Chase et al. showed that global properties like approximate commutation force a function to collapse into a limited set of influential coordinates.
Algorithmic Payoffs: Learning and Optimization
When a function class is proven to have concentrated Fourier energy, it opens the door to highly efficient algorithms. Instead of searching the entire exponential space of features, algorithms can focus exclusively on low-degree polynomial spaces or a small set of influential variables.
In computational learning theory, Mohsen Heidari et al. in Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression leveraged this by showing that restricting the hypothesis space to low-degree polynomials allows $L_2$-polynomial regression to serve as an efficient agnostic PAC learner for $k$-juntas. For broader classes, Vitaly Feldman et al. in Tight bounds on ℓ1 approximation and learning of self-bounding functions used a generalization of Friedgut's theorem to derive more efficient PAC and agnostic learning algorithms for self-bounding functions based on improved $\ell_1$ polynomial approximations.
Beyond learning, this principle simplifies complex continuous and geometric problems. In stochastic optimization, Gözde Özcan et al. in Stochastic Submodular Maximization via Polynomial Estimators used low-degree polynomial estimators to model complex submodular functions, eliminating sampling noise and accelerating greedy maximization algorithms. In formal verification, Tobias Ladner et al. in Exponent Relaxation of Polynomial Zonotopes and Its Applications in Formal Neural Network Verification exploited the fact that high-order polynomials behave similarly over the unit interval, allowing them to substitute complex dependencies with simpler linear factors to prevent exponential complexity during neural network safety checks.
Even the analysis of complex expectations becomes tractable. As shown by Daniel M. Kane et al. in A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length, the expectation of a polynomial threshold function applied to a nearly linear polynomial can be accurately approximated by a polynomial in the original coefficients, providing a tool to fool complex threshold functions with short pseudorandom seeds.
The Boundaries of Junta Approximation
While junta approximation is a remarkably versatile tool, it has fundamental limits. Not every function that appears simple can be reduced to a few variables.
A long-standing conjecture suggested that all monotone Boolean functions computable by low-depth decision trees could be closely approximated by juntas. However, Daniel Kane et al. in A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta disproved this by constructing a complex monotone function that requires an exponentially large junta relative to its tree depth, demonstrating that low depth alone does not guarantee low variable dependence.
Furthermore, the inherent limitation of junta approximations can be turned on its head to prove hardness results. Because low-complexity linear and semidefinite relaxations are structurally limited to capturing local variable dependencies, they can be modeled as approximate juntas. In Approximate Constraint Satisfaction Requires Large LP Relaxations, Siu On Chan et al. showed that functions derived from polynomial-sized linear programs can be approximated by juntas, establishing unconditional lower bounds on the size of LPs needed to solve constraint satisfaction problems. Similarly, Gábor Braun et al. in The matching problem has no small symmetric SDP used junta approximations over large combinatorial spaces to prove that the matching problem cannot be compactly represented or closely approximated by small symmetric semidefinite programs.
Ultimately, junta approximation works because it uncovers a profound truth about many high-dimensional mathematical structures: complexity is often an illusion generated by a vast sea of irrelevant variables, and the core behavior can be distilled down to a vital few.
Key Foundational Work
Improved Approximation of Linear Threshold Functions (2009) — contributed 3 concept elements to this direction.
Extracting Propositions from Trained Neural Networks (1997) — contributed 1 concept elements to this direction.