Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett · 2025
Read Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis by Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13963.txt.
Introduction
Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett wrote this paper in two thousand twenty-five. It asks how much is lost when a Boolean function is matched roughly rather than exactly, when both forms are polynomials in the De Morgan basis.
A classic result ties the exact and rough degrees of such polynomials close together. For sparsity, the count of terms, far less was known. The authors prove the exact and rough sparsity stay close at a log scale, and the same holds for the total weight of the terms. In the Fourier basis the twin claim is false, so the basis matters. The proof rests on a new random restriction method that adapts as it goes.
Catalog record
| CREATOR | Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13963
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett Abstract A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to other complexity measures like sparsity of the polynomial representation, or total weight of the coefficients, remains poorly understood. In this work, we consider this problem in the De Morgan basis, and prove an analogous result for the sparsity of the polynomials at a logarithmic scale. Our result further implies that the exact ℓ 1 \ell_{1} norm and its approximate variant are also similarly related to each other at a log scale. This is in contrast to the Fourier basis, where the analog of our results are known to be false. Our proof is based on a novel random restriction method. Unlike most existing random restriction methods used in complexity theory, our random restriction process is adaptive and is based on how various complexity measures simplify during the restriction process. 1 Introduction Polynomial representations of Boolean functions have been invaluable in theoretical computer science and discrete mathematics. While the representation could use any field, in this work we consider only polynomials over the reals. Two bases are particularly prominent. The first arises naturally by viewing the domain of Boolean functions as \{0,1\}^{n} , and hence, every multilinear monomial just represents the Boolean \and of a subset of variables. This is known as the De Morgan basis . The other basis comes about by viewing the domain as \{1,-1\}^{n} which is a simple linear transformation of \{0,1\}^{n} that maps 0\mapsto 1 and 1\mapsto-1 . In this basis, called the Fourier basis , each monomial represents the Boolean parity of a subset of variables. Two natural complexity measures show up in either basis: the degree and sparsity of the representation. As every Boolean function has a unique representation in either basis, it is usually quite straightforward to determine the degree and sparsity of the unique representation for a function f , which we denote by \deg(f) and \textrm{spar}(f) in the De Morgan basis, and by \deg^{\oplus}(f) , and \textrm{spar}^{\oplus}(f) in the Fourier basis. The linear invertible mapping from one basis to the other ensures that for every f , \deg(f)=\deg^{\oplus}(f) . But sparsity can be very sensitive to the basis chosen. For example, the n -bit AND function has sparsity 1 in the De Morgan basis and 2^{n} in the Fourier basis; and the n -bit Parity function has sparsity 1 in the Fourier basis and 2^{n} in the De Morgan basis. We understand reasonably satisfactorily exact polynomial representations of Boolean functions. However, when we turn to approximations, the picture becomes subtler. Classical approximation theory deals with polynomials that point-wise approximate functions. In an influential work, Nisan and Szegedy [ 44 ] introduced this notion to the study of Boolean functions. In particular, they defined the complexity measure of approximate degree of a Boolean function f , denoted by \widetilde{\textrm{deg}}(f) , to be the smallest degree needed by a polynomial to point-wise approximate f to within a constant distance that is, by default, taken to be 1/3 . Observe that the same reasoning as applied above for exact degree implies that approximate degree of a function is also a measure that is independent of the basis. The notion of approximate degree has had tremendous impact in computer science as it is related to many other complexity measures including the randomized and quantum query complexity of f [ 15 , 5 , 2 , 16 , 17 ] and the quantum and classical communication complexity of appropriately lifted functions [ 14 , 46 , 50 , 48 , 19 , 42 , 6 , 49 ] . It has also found applications in learning theory [ 38 , 36 ] , differential privacy [ 51 , 18 ] , secret sharing [ 10 , 11 ] , and many other areas. Unlike exact degree, getting tight bounds on approximate degree often turns out to be challenging. However, Nisan and Szegedy proved a remarkable structural result that for every total Boolean function f , the approximate and exact degree of f are polynomially related to each other. One of the striking applications of this result is the polynomial equivalence of quantum and classical query models for total Boolean functions, first derived by Beals et al. [ 5 ] . In a much more recent work, building upon Huang’s breakthrough proof [ 33 ] of the sensitivity conjecture, Aaronson et al. [ 1 ] finally gave a tight relationship between the two measures by showing that \deg(f)=O(\widetilde{\textrm{deg}}(f))^{2} . The tightness is witnessed by the Boolean \and and Or functions. Given Nisan and Szegedy’s result, one naturally wonders if approximation could reduce sparsity needed for total functions. In the Fourier basis, it is known that approximation does reduce sparsity exponentially. For instance, the Fourier sparsity of the n -bit \and function is 2^{n} . However, it can be shown that its Fourier approximate-sparsity is O(n^{2}) (implicit in Bruck and Smolesnky [ 12 , appendix] and explicit in [ 23 , Lemma 2.8] ). Surprisingly, the question if approximation helps significantly in the De Morgan basis remained unaddressed. Very recently, Knop et al. [ 39 ] conjectured that in the De Morgan basis, approximation should not significantly reduce sparsity for any total Boolean function. Our main result, stated below, confirms this conjecture. We denote by \widetilde{\textrm{spar}}(f) , the approximate-sparsity of f in the De Morgan basis. Theorem 1.1 (Main Theorem) . For every total Boolean function f:\{0,1\}^{n}\to\{0,1\} , we have \log(\textrm{spar}(f))=O\big(\log(\widetilde{\textrm{spar}}(f))^{2}\cdot\log n\big). Before we continue, let us remark on the tightness of this result. Remark 1.2 . The n -bit Or function has sparsity 2^{n}-1 and approximate sparsity 2^{O(\sqrt{n}\log n)} , showing that exponential gaps may exist between the two measures in the absolute scale. It is thus necessary to consider the log scale as done in Theorem 1.1 for seeking polynomial relationship between the two measures. The example of Or also demonstrates the tightness of our bound up to poly-logarithmic factors. Finally, the appearance of the ambient dimension n in our result is unavoidable. Consider the function \mbox{{\sc Thr}}^{n}_{n-1}:\{0,1\}^{n}\to\{0,1\} defined by \mbox{{\sc Thr}}^{n}_{n-1}(x)=1\quad\text{if and only if}\quad|x|\geq n-1, namely, the function evaluates to 1 if the input has at most one zero. It’s simple to verify that its exact sparsity is n+1 , and we show in section 3.3 that its approximate sparsity is O(\log n) , implying that an additive O(\log n) or multiplicative O\left(\frac{\log n}{\log\log n}\right) factor is necessary in Theorem 1.1 . One of the motivations of Nisan and Szegedy to study approximate degree was to relate this measure with decision tree complexity. Let \textrm{D}^{dt}(f) and \textrm{R}^{dt}(f) denote the deterministic and randomized bounded-error decision tree complexities of f respectively. Their result, along with the recent improvement of [ 1 ] yields the following relationship. Theorem 1.3 (Nisan-Szegedy [ 44 , Theorem 1.5] + Aaronson et al. [ 1 ] ) . For every total Boolean function