On Fourier analysis of sparse Boolean functions over certain Abelian groups

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal

TL;DR

This paper generalizes the concept of "Fourier sparsity" for Boolean functions from the familiar binary hypercube to more general finite Abelian groups. The authors establish new structural properties of these sparse functions and use them to design an efficient algorithm for testing sparsity, along with a theoretical lower bound on the number of queries required for such tests.

What Problem Does This Paper Address?

Boolean functions are fundamental in computer science, modeling decision tasks. Analyzing their "Fourier sparsity" – having only a few non-zero coefficients in their Fourier transform – has been crucial for understanding their complexity and for applications in areas like learning theory and cryptography. A key result by Gopalan et al. (2011) established "granularity" for Fourier coefficients of sparse Boolean functions over binary hypercubes (ℤ₂ⁿ), meaning coefficients have specific, structured magnitudes. This paper tackles the challenge of extending these powerful structural results and related algorithms to a broader class of domains: general finite Abelian groups. The authors aim to understand the structure of sparse functions on these more complex algebraic structures and to develop efficient methods for testing this sparsity, while also establishing fundamental limits on such testing.

Methods

The paper introduces novel techniques to generalize the notion of "granularity" for Fourier coefficients of Boolean functions over arbitrary finite Abelian groups. This involves leveraging group theory and algebraic number theory. They prove structural theorems that characterize functions that are "close" to being sparse. A key algorithmic contribution is an efficient, non-adaptive sparsity testing algorithm for Boolean functions over these groups. This algorithm's design is informed by the new structural results. Additionally, the authors generalize the concept of "Boolean degree" to Abelian groups and use this generalization to prove a lower bound on the query complexity of adaptive sparsity testing algorithms. The proofs often employ probabilistic methods and carefully constructed arguments to handle the complexities of general Abelian groups compared to the simpler vector space structure of binary hypercubes.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Generalizing Granularity: The core insight is that the "granularity" property of Fourier coefficients, previously known for binary hypercubes, can be generalized to arbitrary finite Abelian groups. This allows for a deeper understanding of the structure of sparse functions in these more general settings.
  • Lower Bounds for General Groups: A significant finding is that while Fourier coefficients of sparse functions over binary hypercubes have a lower bound related to s (the sparsity), this direct relationship doesn't hold for general Abelian groups. The paper derives a more complex, group-dependent lower bound, demonstrating that the structure of the group itself plays a crucial role.
  • Efficient Sparsity Testing: By leveraging the new structural theorems, the authors design an efficient algorithm to test if a given Boolean function is sparse or "far" from being sparse. This is a practical contribution with implications for algorithm design and analysis.
  • Lower Bound on Adaptive Testing: The generalization of "Boolean degree" to Abelian groups is a novel theoretical tool that leads to a fundamental lower bound on the number of queries an adaptive algorithm needs to distinguish sparse functions. This highlights the inherent difficulty of testing sparsity in these settings.

Key Results

  • Structural Theorems: The paper provides two main structural theorems for approximately Fourier-sparse Boolean functions over finite Abelian groups. These theorems generalize the "granularity" concept and establish bounds on the l₂ distance to an actual sparse function.
  • Fourier Coefficient Lower Bound: A generalized lower bound on the absolute value of non-zero Fourier coefficients of an s-sparse function is derived, which is dependent on the group's structure (specifically, its exponent ∆). This bound is shown to be potentially weaker than the s-dependent bound for binary hypercubes, suggesting that some properties are group-specific.
  • Sparsity Testing Algorithm: An efficient, non-adaptive algorithm is presented that tests if a function is s-sparse or ε-far from s-sparse with a query complexity of poly(s, 1/ε, log ∆).
  • Adaptive Sparsity Testing Lower Bound: An Ω(√s) lower bound is proven for adaptive sparsity testing algorithms over general Abelian groups.

Limitations and Future Work

The paper acknowledges that the derived lower bound on Fourier coefficients is group-dependent and weaker than the binary hypercube case, suggesting that further work might explore tighter bounds or specific group structures. The authors also pose a question about whether a better (∆-dependent) lower bound on the query complexity of adaptive sparsity testing algorithms can be shown. The work focuses on Boolean-valued functions; extending these results to more general functions could be a future direction.

Summary updated

Abstract

Given an Abelian group G, a Boolean-valued function f: G -> {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. proved "Granularity" for Fourier coefficients of Boolean valued functions over Z_2^n, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over Z_2^n which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups G of the form,G:= Z_{p_1}^{n_1} \times ... \times Z_{p_t}^{n_t}, for distinct primes p_i. We also obtain a lower bound of the form 1/(m^{2}s)^ceiling(phi(m)/2), on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where m=p_1 ... p_t, and phi(m)=(p_1-1) ... (p_t-1). We carefully apply probabilistic techniques from Gopalan et al., to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over Z_p^n, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is 1/omega(n). The "Granularity" result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over Z_2^n are 1/O(s). So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient testing algorithm for Fourier-sparse Boolean functions, thata requires poly((ms)^phi(m),1/epsilon)-many queries. Further, we prove an Omega(sqrt{s}) lower bound on the query complexity of any adaptive sparsity testing algorithm.
BibTeX
@inproceedings{chakraborty2024fourier,
  author = {Sourav Chakraborty and Swarnalipa Datta and Pranjal Dutta and Arijit Ghosh and Swagato Sanyal},
  title = {{On Fourier analysis of sparse Boolean functions over certain Abelian groups}},
  booktitle = {MFCS},
  year = {2024},
  url = {https://openreview.net/forum?id=8rEgAr9fpu},
}
Figure