Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube

Yuval FilmusChic. J. Theor. Comput. sci 2016

TL;DR

This paper extends a fundamental result in Boolean function analysis, the Friedgut-Kalai-Naor (FKN) theorem, from the entire Boolean cube to "slices" – specific subsets of the cube. The authors prove that functions on these slices that are close to linear functions can be approximated by simple "junta" functions (depending on a few variables), with the number of variables depending on how "thin" the slice is.

What Problem Does This Paper Address?

The Friedgut-Kalai-Naor (FKN) theorem is a cornerstone in the analysis of Boolean functions. It states that any Boolean function on the standard Boolean cube $\{0,1\}^n$ that is "close" to a linear function (an affine function) must also be close to a "dictatorship" function – one that depends on at most a single input variable. This is a powerful structural result. However, much of this theory was developed for the entire Boolean cube, which has a nice product structure.

This paper tackles the challenge of extending this powerful FKN theorem to "slices" of the Boolean cube. A slice, denoted as $\binom{[n]}{k}$, is the set of all binary vectors of length $n$ with exactly $k$ ones. These slices are non-product domains and lack a canonical Fourier basis, making them more complex to analyze. The authors aim to prove an analogous FKN theorem for these slices, showing that functions close to linear on a slice can be approximated by simple functions, specifically maximum or minimum functions over a small subset of variables.

Methods

The core of the paper's methodology lies in adapting and extending the techniques used in the original FKN theorem to the slice setting. Key approaches include:

  • Random Sub-cube Method: This is a central technique. The authors show how to reduce the problem on a slice to the FKN theorem on the standard Boolean cube by considering random sub-cubes within the slice. These sub-cubes are isomorphic to smaller Boolean cubes, allowing the application of the classical FKN theorem.
  • Analysis of Affine Functions on Slices: The paper carefully analyzes the structure of affine functions on slices, showing that their coefficients are concentrated around a few values. This is crucial for approximating the original function.
  • Variance Analysis: The authors employ variance formulas to bound the "noise" or deviation of the function from its approximating junta.
  • Hypergeometric Distribution Analysis: A significant portion of the proof involves detailed analysis of hypergeometric random variables, which arise naturally when considering sums of independent Bernoulli random variables on slices. This is used to establish bounds on the size of the approximating junta.
  • Extension of FKN to Biased Measures: As a byproduct, the paper also derives a uniform version of the FKN theorem for the biased Boolean cube (where inputs are not uniformly distributed), which is a significant result in itself.

Datasets

Not discussed in the paper. The paper deals with theoretical functions on abstract domains (Boolean cube and its slices) rather than empirical datasets.

Key Insights and Ideas

  • The "Thin Slice" Problem: The most striking insight is how the structure of the slice affects the FKN theorem. When a slice is "thin" (i.e., $k/n$ is close to 0 or 1), the guarantee weakens. Instead of a dictatorship (one variable), we can only guarantee approximation by a junta (a small number of variables). This is because for thin slices, sums of variables behave similarly to maximums of variables.
  • Universality of the Junta Property: The paper demonstrates that even on these more complex slice domains, functions close to linear still exhibit a strong structural property: they can be approximated by functions depending on a limited number of variables.
  • Bridging the Gap: The random sub-cube method is a clever way to leverage existing powerful results (FKN on the Boolean cube) to solve problems on more intricate structures (slices).
  • Uniformity in Biased Measures: The derivation of a uniform FKN theorem for biased measures is a valuable contribution, providing error bounds that don't depend on the bias parameter $p$.

Key Results

  • Main Theorem (Slice FKN): For a slice $\binom{[n]}{k}$ where $2 \le k \le n-2$ and $p = \min(k/n, 1-k/n)$, if a Boolean function $f$ is $\epsilon$-close to an affine function, then either $f$ or $1-f$ is $O(\epsilon)$-close to a function of the form $\max_{i \in S} x_i$ (or $\min_{i \in S} x_i$), where the size of the set $S$ is at most $O(\sqrt{\epsilon/p})$.
  • Junta Approximation: When $\epsilon$ is small relative to $p^2$ (specifically, $\epsilon < Cp^2$ for some constant $C$), the size of $S$ is guaranteed to be at most 1, recovering the dictatorship property.
  • Uniform FKN for Biased Cube: The paper derives a uniform version of the FKN theorem for the biased Boolean cube, where error bounds are uniform over the bias parameter $p$.

Limitations and Future Work

  • Dependence on $p$ for Junta Size: The paper highlights that for thin slices (small $p$), the size of the approximating junta can grow with $1/\sqrt{p}$. This dependence is inherent to the problem, as demonstrated by examples where sums are close to maximums.
  • Constant Factors: As is common in theoretical computer science, the $O(\epsilon)$ bounds hide constant factors that might depend on $n$, $k$, or $p$.
  • Future Work: The authors suggest that it might be easier to prove the uniform FKN theorem for the biased Boolean cube directly, rather than as a corollary of their slice theorem. They also mention that similar arguments can be applied to other combinatorial structures like permutations. Further exploration of these connections and potential improvements to the constant factors would be valuable.

Summary updated

BibTeX
@article{filmus2016friedgut,
  author = {Yuval Filmus},
  title = {{Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube}},
  journal = {Chic. J. Theor. Comput. sci},
  year = {2016},
}
Figure