WorksComputer Science
Fourier Entropy Bounds via Approximations
Abstract
We establish upper bounds on the Shannon entropy of the Fourier distribution of Boolean functions. We prove that where denotes the minimum spectral norm of a pointwise -approximant to . This implies , where is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of as , with nonnegative weights and affine subspaces , we prove The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of with small spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.
Introduction
The Fourier Entropy-Influence Conjecture (FEIC) of Friedgut and Kalai [9] proposes a fundamental relation between the Fourier spectrum of a Boolean function and its sensitivity to changes in the input. For , Parseval’s identity gives , so the squared Fourier coefficients define a probability distribution on subsets of . Two natural quantities associated with this distribution are its Shannon entropy () and the expected size of a set drawn from it ():
The latter quantity is the total influence of , or equivalently, its average sensitivity. Throughout the paper, logarithms are to base two unless otherwise indicated, and .
Conjecture 1 (Fourier Entropy-Influence Conjecture [9]). There is a universal constant such that every Boolean function satisfies
The conjecture asserts that a Boolean function with small total influence cannot have its Fourier weight spread over too many coefficients in an information-theoretic sense. Its original motivation came from threshold phenomena for monotone graph properties [9]. A positive resolution would strengthen sharp-threshold estimates [3 KKL${}^{+}$20a] and imply the Kahn–Kalai–Linial theorem [16]; see [25 KKL${}^{+}$20a, ACK${}^{+}$21] for these implications. The conjecture also connects the analysis of Boolean functions with learning theory through sparse approximation in the Fourier basis.
A central example of this connection is Mansour’s conjecture [21]. A -term DNF is a disjunction of at most conjunctions of literals. Although its Fourier expansion can have exponentially many non-zero coefficients, the conjecture predicts that a polynomial number of them captures almost all of its Fourier weight.
Conjecture 2 (Mansour’s conjecture [21]). Let be computed by a -term DNF, where . For every , there is a family such that
By Parseval’s identity, this is a statement about approximation by sparse Fourier polynomials in squared distance. More generally, an entropy bound implies that Fourier coefficients carry at least of the weight. Indeed, the coefficients whose squared magnitude is below have total weight at most . Consequently, FEIC would imply Mansour’s conjecture using the bound for -term DNFs [25, 1]. Combined with the query-learning algorithm of Gopalan, Kalai, and Klivans [13], Mansour’s conjecture would give a polynomial-time algorithm for agnostically learning polynomial-size DNFs under the uniform distribution, with query access and any fixed accuracy. This is a long-standing open question in computational learning theory [12].
One approach towards FEIC is to bound Fourier entropy by other measures of Boolean function complexity. Chakraborty, Kulkarni, Lokam, and Saurabh [6] obtained bounds in terms of average decision-tree depth, including its parity-query analogue. Arunachalam, Chakraborty, Koucký, Saurabh, and de Wolf [1] strengthened these bounds to , where is the average codimension of a monochromatic affine subspace partition. They also bounded Fourier min-entropy by the logarithm of approximate spectral norm and by randomized parity-query complexity. Their corresponding bounds for Rényi entropy of order incur a factor that diverges as tends to zero, and therefore do not give bounds on Shannon entropy. These results leave two natural questions: can the approximation and randomized-query bounds be extended to Shannon entropy, and can the partition bound be expressed using only one output side or a nonnegative overlapping representation?
Our results
We answer both questions affirmatively. Our bounds extend the approximate spectral-norm and randomized-query results of [1] to Shannon entropy, and strengthen their partition bound to one-sided average unambiguous certificates and exact conical representations. Our proofs use two analytic ingredients: an entropy bound from a sequence of increasingly accurate approximants, and moment inequalities obtained by interpolation. The approximation method also gives a linear entropy lower bound for bounded-error, entanglement-assisted quantum communication. We state these results below and then describe the general analytic techniques behind them.
Approximate spectral norm and randomized query complexity. Recall that is the least spectral norm of a polynomial satisfying at every input. The elementary inequality bounds entropy by the spectral norm of the exact function. We show that a uniform approximation at any fixed error below one suffices. In particular, Theorem 3.2 gives
For any other fixed , the same statement holds with a constant depending only on . Thus, the Fourier distribution has small Shannon entropy whenever admits an -approximating polynomial of small spectral norm, even if the spectral norm of itself is much larger.
This yields an entropy bound in terms of bounded-error randomized query complexity. Let denote the minimum worst-case number of parity queries needed to compute , with error at most on every input. Theorem 3.3 states that
In particular, for ordinary randomized query complexity. The expected output of a randomized parity-decision tree is an approximating polynomial whose spectral norm is at most ; applying (1) at constant error proves the bound. Equations (1) and (2) extend the corresponding results of [1] from min-entropy and Rényi orders greater than one to Shannon entropy.
One-sided average unambiguous certificates. For , consider a partition of into affine subspaces. Its average cost is
and minimizing this quantity gives . The average is taken over the entire uniform input space, with zero cost outside the specified output side. Theorem 4.3 gives
Restricting to subcube partitions gives the same conclusion for ordinary one-sided unambiguous certificates. In particular, an unambiguous DNF representation suffices to control the entropy by the average width of its satisfied term, without constructing a partition of the other output side. This improves the dependence on the complexity measure in [1]: their two-sided bound uses , and their one-sided extension includes an additional maximum-codimension term.
Average conical junta degree. We extend the unambiguous certificate bound to exact non-negative representations whose terms may overlap. In the usual definition, a conical junta is a non-negative linear combination of conjunctions [11]. We also allow indicators of affine subspaces, and consider representations
The average conical junta degree of this representation is
This is the uniform-input average of the local weighted degree. For conjunctions, Goös and Jayram [11] study the maximum over inputs of that local quantity; our measure instead averages over inputs. Minimizing over exact representations defines . Theorem 4.5 states that
An unambiguous partition is a representation by disjoint indicators with unit weights, so (4) generalizes (3). The exact identity is essential: on the represented output side the weights of the containing subspaces must sum to one. An arbitrary DNF need not satisfy this condition, so the result does not by itself give the entropy bound required for Mansour’s conjecture.
Quantum communication complexity. Our approximation method also bounds the entropy of squared singular values. Let be a total sign matrix and let be probability vectors on . The matrix has squared Frobenius norm one. Write for the Shannon entropy of its squared singular values. Theorem 5.1 shows that, for every fixed ,
where arbitrary prior entanglement is allowed and is independent of the matrix dimensions and the product weights. For the XOR matrix , where denotes coordinatewise multiplication on , uniform weights give the Fourier distribution of as the squared singular-value distribution. Consequently,
Thus Fourier entropy provides a lower bound on bounded-error quantum communication for XOR functions, even with shared entanglement.
Analytic ingredients. The approximation theorem, Theorem 3.1, applies to any with . Suppose that for every integer there is an approximant such that
where , , and . Then , where denotes the entropy functional without requiring the squared coefficients to sum to one. The proof groups coefficients according to the first accuracy at which they are well approximated. The approximation error bounds the Fourier weight of the remaining groups, while the spectral norm controls their entropy. Error reduction by majority supplies the required sequence of approximants from a constant-error approximating polynomial to give (1). For communication protocols, error reduction and the factorization-norm estimate of Linial and Shraibman [20] supply analogous approximants to the singular-value vector to give (5).
Our second ingredient is an interpolation inequality for sums. If with the nonzero pairwise orthogonal, set and . Theorems 4.1 and 4.2 give
The first inequality follows from the Riesz–Thorin interpolation theorem; differentiating at , where equality holds, yields the second. For the one-sided unambiguous representations, ’s are orthogonal, and hence Theorem 4.2 gives (3). Theorem 4.4 replaces orthogonality by the condition that the Gram matrix has a diagonal majorant , where . It gives the same moment bound with in place of , and the entropy bound when . For nonnegative summands in an exact conical representation, the row sums of provide such a majorant with the required equality. This permits overlapping summands and gives (4).
Prior work
Several works have established FEIC for structured classes of Boolean functions. O’Donnell, Wright, and Zhou [25] proved it for symmetric functions and read-once decision trees. Chakraborty, Kulkarni, Lokam, and Saurabh [6] and O’Donnell and Tan [24] independently established it for read-once AND/OR formulas. The latter work proves a composition theorem that also handles read-once formulas over bounded-arity gates. Wan, Wright, and Wu [29] used a source-coding interpretation of FEIC to reprove the composition theorem and to show that functions computed by read- decision trees satisfy . Shalev [26] improved the dependence on to . In particular, these results verify FEIC for every fixed read bound. In a very recent preprint, Shmalo [27] establishes FEIC for every linear threshold function.
There are also results for random functions. Klivans, Lee, and Wan [19] proved the FEI conjecture for random DNF formulas. Das, Pal, and Visavaliya [8] verified FEIC with high probability for a uniformly random Boolean function. Chakraborty, Karmalkar, Kundu, Lokam, and Saurabh [5] proved analogous results for random linear threshold functions. Shalev [26] established FEIC when either the influence is too low or the entropy is too high. In the other direction, constructions of Hod [15] show that any universal constant in FEIC must exceed 6.45, even for monotone functions.
Kelman, Kindler, Lifshitz, Minzer, and Safra [18] obtained general bounds that bring Fourier concentration closer to the prediction of FEIC. Among other results, they show
They also obtain bounds on large Fourier coefficients, with applications to learning and sharp thresholds. Han [14] proves the bound,
The proof estimates Fourier moments iteratively and then obtains entropy by differentiation. Our interpolation inequalities also pass from moments to entropy via differentiation, but use orthogonal or non-negative decompositions in place of the individual influences.
A different line of work bounds entropy by the complexity of a description of the function. Chakraborty et al. [6] bounded Fourier entropy in terms of average decision-tree depth, including its parity-query analogue. Arunachalam, et al. [1] strengthened these estimates to
where is the minimum average codimension of a monochromatic affine subspace partition. For ordinary subcubes, this gives a bound by average unambiguous certificate complexity.
Comparison with previous work
The distinction between average cost and maximum cost is central to the unambiguous certificate bounds. For a partition , write for its average cost and . The one-sided bound in [1 Theorem 1.7] is
Our bound is , with no dependence on . The randomized query bound addresses a different extension, allowing bounded error; it should be distinguished from the earlier bounds using the average depth of an exact tree.
The approximation theorem controls the contribution of small Fourier coefficients by combining approximants at all accuracies. It therefore bounds the full Shannon entropy. In contrast to the influence-based estimates (6) and (7), our hypotheses concern the spectral norms of approximants or the average cost of an exact decomposition.
For communication complexity, Montanaro and Winter [22] proved an exact-computation lower bound of and a bounded-error bound of for -bit inputs, allowing product weights and prior entanglement. For uniform sign matrices, Linial and Shraibman [20 Theorem 30] obtained
Our bound (5) removes this denominator. The improvement is relevant when is small relative to . We use the same protocol factorization estimate underlying the Linial–Shraibman method. The improvement is in deriving a dimension-independent entropy consequence. Our proof combines approximations at all accuracies and avoids a dimension-dependent loss.
Organization. Preliminaries are in § 2. § 3 proves the approximation theorem (Theorem 3.1) and its consequences for approximate spectral norm (Theorem 3.2) and randomized queries (Theorem 3.3). § 4 develops the moment and entropy inequalities (Theorems 4.1, 4.2, and 4.4) and applies them to one-sided certificates (Theorem 4.3) and conical juntas (Theorem 4.5). § 5 proves the quantum communication lower bound (Theorem 5.1).
Preliminaries
We recall some definitions and basic facts from analysis of Boolean functions, referring to [23, 28] for more. Consider the space of all functions from to equipped with the inner product defined as
For , the character function is defined as . Then the set of character functions forms an orthonormal basis for the space of all complex-valued functions on . Hence, every complex-valued function has a unique Fourier expansion
The degree of , denoted , is defined as . The spectral norm of is defined to be . The Fourier weight of a function on a set of coefficients is defined as . For , the -approximate spectral norm of a Boolean function is defined as
We will use to denote the function that maps to its Fourier coefficient . We note a well-known fact that follows from the orthonormality of the character functions.
Fact 2.1 (Plancherel’s Theorem). For any ,
In particular, if is Boolean-valued and , we have Parseval’s Identity , which in turn equals . Hence and we can view as a probability distribution, which allows us to discuss the Fourier entropy and min-entropy of the distribution , defined as
Definition 2.2. For a Boolean function , its Fourier entropy (denoted ) and min-entropy (denoted ) are
Similarly, we can also define the Rényi Fourier entropy.
Definition 2.3 (Rényi Fourier entropy). For , and , the Rényi Fourier entropy of of order is defined as
It is known that in the limit as , is the (Shannon) Fourier entropy (see [7 Chapter 17, Section 8]) and when , observe that converges to . It is easily seen that
For an arbitrary function , we will define
Note that need not equal 1. In the special case of Boolean functions we have the following relationship.
Lemma 2.4. Let be any Boolean function and (or, ). Then,
where and . Moreover, for all .
For , the influence of a coordinate , denoted , is defined as
where the probability and expectation is taken according to the uniform distribution on and is with the -th bit flipped. The total influence of , denoted , is
In terms of the Fourier coefficients of , it can be shown, e.g., [16], that , and therefore
The variance of a real-valued function is given by . It easily follows that . We now introduce some basic complexity measures of Boolean functions which we use often, referring to [4] for more.
Sensitivity For , the sensitivity of at , denoted , is defined to be the number of neighbors of in the Boolean hypercube (i.e., is obtained by flipping exactly one bit of ) such that . The sensitivity of is . The average sensitivity of is defined to be . By the linearity of expectation observe that
so the average sensitivity of equals the total influence of . As a result, the FEI conjecture asks if for every Boolean function .
Certificate complexity For , the certificate complexity of at , denoted , is the minimum number of bits in that needs to be fixed to ensure that the value of is constant. The certificate complexity of is . The minimum certificate complexity of is . The 0-certificate complexity of is . Similarly, the 1-certificate complexity of is . Observe that for every , . This gives and where denotes the average certificate complexity of . As before, the average is taken with respect to the uniform distribution on .
Parity-certificate complexity Analogously, we define the parity-certificate complexity of at as the minimum number of parities on the input variables one has to fix in order to fix the value of at , i.e.,
where is the co-dimension of the affine subspace . It is easily seen that . We also define , and .
Unambiguous certificate complexity We now define the unambiguous certificate complexity of . Let be a partial assignment. We refer to
as the subcube generated by . We call a subcube of if there exists a partial assignment such that and the co-dimension of is the number of bits fixed by , i.e., . A set of subcubes partitions if the subcubes are disjoint and they cover , i.e., for and .
An unambiguous certificate , also referred to as a subcube partition, is a set of subcubes partitioning . We say computes a Boolean function if is constant on each (i.e., is the same for all ). For an unambiguous certificate , the unambiguous certificate complexity on input equals for the satisfying . Define the average unambiguous certificate complexity of with respect to as
Then, the average unambiguous certificate complexity of is defined as
where the minimization is over all unambiguous certificates for . We also define the one-sided version of these measures. Let be such that, for , is an unambiguous -certificate, i.e., is a subcube partition of . Then, define and note that . We therefore define the average unambiguous -certificate complexity of as
where the minimization is over all unambiguous -certificates for . Observe that . Finally, the unambiguous certificate complexity of is
Note that since unambiguous certificates are more restricted than general certificates, we have .
An unambiguous -certificate for is defined to be a collection of monochromatic affine subspaces that together partition the space . It is easily seen that a subcube is also an affine subspace. Analogously, for an unambiguous -certificate , on an input , for the satisfying , and . Similarly, we define , , , and .
DNFs A DNF (disjunctive normal form) is a disjunction (OR) of conjunctions (ANDs) of variables and their negations. An unambiguous DNF is a DNF that satisfies the additional property that: on every -input, exactly one of the conjunctions outputs . Note that an unambiguous DNF for is equivalently an unambiguous 1-certificate for .
Approximate degree The -approximate degree of , denoted , is defined to be the minimum degree among all multilinear real polynomials such that for all . Usually is chosen to be , but it can be chosen to be any constant in , without significantly changing the model.
Deterministic decision trees A deterministic decision tree for is a rooted binary tree where each node is labelled by and the leaves are labelled with an output bit . On input , the tree proceeds at a node with label by evaluating the bit and continuing with the subtree corresponding to the value of . Once a leaf is reached, the tree outputs a bit. We say that a deterministic decision tree computes if for all its output equals .
A parity-decision tree for is similar to a deterministic decision tree, except that each node in the tree is labelled by a subset . On input , the tree proceeds at a node with label by evaluating the parity of the bits for and continues with the subtree corresponding to the value of . Note that if the subsets at each node have size , then we get the standard deterministic decision tree model.
Randomized decision trees A randomized decision tree for is a probability distribution over deterministic decision trees for . On input , a decision tree is chosen according to , which is then evaluated on . The complexity of the randomized tree is the largest depth among all deterministic trees with non-zero probability of being sampled according to . One can similarly define a randomized parity-decision tree as a probability distribution over deterministic parity-decision trees for .
We say that a randomized decision tree computes with bounded-error if for all its output equals with probability at least . (respectively, ) denotes the complexity of the optimal randomized (respectively, parity) decision tree that computes with bounded-error, i.e., errs with probability at most .
Conical Juntas Let , a conical junta, be a weighted sum over conjunctions of literals with weights . We say that a Boolean function is represented by a conical junta if . More generally, we will consider (non-negative) weighted sum over affine subspaces. We define the average conical junta degree of , denoted , equals . Then, the average conical junta degree of is the minimum average conical junta degree over all conical junta representations . Similar measures were studied in [11].
Theorem 2.5 (The Reisz-Thorin Interpolation Theorem [10 Theorem 6.27]). Let and be non-empty finite sets. Further let be a linear map, and for be such that for every ,
Then, for every ,
Approximants
Theorem 3.1. Let with . Suppose that , , , and for any integer , there is a function such that
Then,
where .
Proof. For each , define the following set of good monomials
Using 's we partition the set of non-zero Fourier coefficients as follows: for each ,
Since , as , every fixed non-zero coefficient eventually becomes good, and thus 's partitions the set of non-zero Fourier coefficients of .
Let us define the Fourier weight on the part , i.e., . Also define and . From the definitions it follows that and
where the last inequality follows from (12). Further, we have
We also have for , , and therefore, . We can thus bound as follows
where the first inequality follows from the Jensen’s inequality using the concavity of log. We now bound each term in (18) to obtain the bound in (13). We have
and
where we used equations (16), (17), (12) and the Jensen’s inequality to simplify. Substituting them back in (18) we obtain
Proof.
As an application we show that Fourier-entropy is bounded by the logarithm of -approximate spectral norm.
Theorem 3.2. Let be a Boolean function. Then, for , .
Proof. Without loss of generality, assume . Let be a -approximating polynomial for , and let . Let be the Majority function on variables. Then, define and . It is well known that the following facts holds:
, and hence , while
.
For each , define the approximant . We, therefore, have
It, thus follows from Theorem 3.1,
and therefore,
The second equality follows since is an arbitrary -approximating polynomial.
As a further corollary to Theorem 3.2, we bound the Fourier-entropy by the randomized decision-tree complexity.
Theorem 3.3. Let be a Boolean function and be the randomized parity-decision tree complexity of with error at most . Then, .
Proof. Let be a randomized -decision tree computing . That is, it is a distribution on deterministic -decision trees such that for each input , .
Then, consider the polynomial , where are polynomials representing exactly. Therefore, for each input , and thus . Hence, is a -approximating polynomial for . Furthermore, . The bound now follows from an application of Theorem 3.2.
Moment Inequality
Theorem 4.1. Let and where the non-zero functions are pairwise orthogonal. Define and . Then, for every ,
Equality holds at .
Proof. Define for , and the linear operator by
We now compute the and norms of . We have, by the triangle inequality,
The Orthogonality and Parseval give equality for norm. That is,
Then applying the Reisz-Thorin interpolation theorem (Theorem 2.5), for , we obtain,
Now choose to obtain , and thereby we get
Moreover, it is easily seen from (21) that equality holds at .
We now transfer the moment inequality in Theorem 4.1 to bounds on entropy.
Theorem 4.2. Let and where the non-zero functions are pairwise orthogonal. Define and . Then,
Proof. Define the functions
We have from Theorem 4.1 that for and . Thus for ,
Hence, taking the left-derivative at 2, gives . Computing we have
Multiplying each derivative by and using the inequality , we obtain
Theorem 4.3. Let be a Boolean function. Then, , where for , is the average unambiguous -parity-certificate complexity of .
Proof. Fix (the other case is analogous). Let and be an unambiguous 1-parity-certificate for . Let be the indicator function of the 1-parity-certificate . Then, it follows by unambiguity that and 's are pairwise orthogonal. From, Lemma 2.4 and Theorem 4.2, we have
Since is arbitrary, we obtain .
We now generalize Theorem 4.1 (and Theorem 4.2) to handle the case of conical juntas where the conjunctions may not be orthogonal.
Theorem 4.4. Let and where 's are non-zero functions. Define Gram matrix where , and denote . Suppose there are numbers such that
Then, for every $1\le r\le 2,
If, additionally, the equality holds at , , then
Proof. Define for , and the linear operator by
As before we compute the and norms of . We have, by the triangle inequality,
For norm, we first use Parseval and then (26). That is,
where the first inequality follows from (26) which implies that for all , . Then applying the Reisz-Thorin interpolation theorem (Theorem 2.5), for , we obtain,
Now choose to obtain , and thereby we get
Furthermore, if , then the arguments from the proof of Theorem 4.2 can be applied here too to obtain a similar bound on entropy
We now use Theorem 4.4 to bound Fourier-entropy by the average conical junta degree. This measure is the average of the measure ’average degree’ defined and studied by [11].
Theorem 4.5. Let be a Boolean function. Then,
Proof. Let be represented by a conical junta where 's are conjunctions of literals (or, more generally, indicators of affine subspaces). Recall, . Since Fourier-entropy is invariant under negation, it suffices to show .
Let , where . Furthermore, let be a Gram matrix with . Then, and define the row sums and the diagonal matrix . It is then easily seen that . Indeed, for every ,
Also , , and . Thus, by an application of Lemma 2.4 and Theorem 4.4, we obtain
Application to Quantum Communication Complexity Lower Bound
Let be finite non-empty sets and let be a total sign matrix. The quantity is the minimum worst-case number of qubits communicated by a two-party protocol that outputs with error at most on every input . Arbitrary finite-dimensional prior entanglement and local ancillas are allowed. Bob is the designated output party. For probability vectors and , let
Let be the singular values of . Since
their squares form a probability distribution. Define
with . We now show that supremum over all probability distributions and lower bounds the quantum communication complexity.
Theorem 5.1. For every , there is a constant such that, for every total sign matrix and every pair of probability vectors ,
In particular, for , let , and be uniform distributions, and then we have
For uniform sign matrices, let . Linial–Shraibman prove the bounded-error estimate
in [20 Theorem 30]. Theorem 5.1 removes the denominator and provides a dimension-independent bound. We recall some basics of matrix norms. For a matrix , let denote its trace norm, and let . Define the factorization norm
where are rows. We need the following facts about various norms.
Lemma 5.2 ([2 Corollary IV.2.6]). For every matrix and every pair of probability vectors ,
Lemma 5.3 ([2 Theorem IV.3.4]). If have the same dimensions and are their singular values in decreasing order, then
We also need the following lemma from [20] about -norm of the matrix of acceptance probabilities.
Lemma 5.4 ([20 Lemma 10]). If is the acceptance probability of a protocol with communication
cost , then . For its expected signed output matrix , where is all ones,
We are now ready to prove Theorem 5.1.
Proof of Theorem 5.1. Let be any sign matrix, and assume, without loss of generality, . For every integer , amplify a cost protocol by independent repetition and majority until its error is at most . Let the cost of this amplified protocol be . Let be the probability that this amplified protocol outputs , and define its expected signed output , where is the all-ones matrix. From the correctness of the protocol, we then have
where the second estimate is Lemma 5.4. Let and . Then pointwise approximation (34) imply
Lemma 5.2 gives , and therefore . Let
with singular values listed in decreasing order and zeroes included so all lists have the same length. We therefore have, from Lemma 5.3 and (35),
Moreover, and , so . Now using Theorem 3.1 with and gives
In particular, when is a XOR-matrix of a Boolean function , then Fourier-entropy of lower bounds the quantum communication cost of ,
AI statement. We used several ChatGPT and Claude models over the last few months to explore proof strategies, search for related literature, and revise the manuscript. The authors had a part of the proof idea which was substantially generalized by these AI models. The authors examined these arguments, identified and corrected errors, and significantly simplified proofs and their presentation. The authors take full responsibility for the correctness and content of the paper.
References
- [1]S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, and R. de Wolf. Improved bounds on Fourier entropy and min-entropy. ACM Transactions on Computation Theory, 13(4):22:1–22:40, 2021.
- [2]R. Bhatia. Matrix Analysis. Springer New York, NY, 1997.
- [3]J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geometric and Functional Analysis (GAFA), 7(3):438–461, 1997.DOI
- [4]H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21–43, 2002.DOI
- [5]S. Chakraborty, S. Karmalkar, S. Kundu, S. V. Lokam, and N. Saurabh. Fourier entropy-influence conjecture for random linear threshold functions. In Proceedings of the 13th Latin American Theoretical Informatics Symposium, LATIN 2018, pages 275–289, 2018.arxiv.org/abs/1903.11635
- [6]S. Chakraborty, R. Kulkarni, S.V. Lokam, and N. Saurabh. Upper bounds on Fourier entropy. Theoretical Computer Science, 654:92–112, 2016. The first version appeared as a technical report TR13-052 on ECCC in 2013.
- [7]T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991.
- [8]B. Das, M. Pal, and V. Visavaliya. The entropy influence conjecture revisited, 2011. arxiv:1110.4301.arxiv.org/abs/1110.4301
- [9]E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993–3002, 1996.DOI
- [10]G. B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley and Sons, Inc., 2nd edition, 1999.
- [11]M. Göös and T. S. Jayram. A composition theorem for conical juntas. In 31st Conference on Computational Complexity, CCC 2016, volume 50 of LIPIcs, pages 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.DOI
- [12][GKK08a] P. Gopalan, A. Kalai, and A. R. Klivans. A query algorithm for agnostically learning DNF? In Proceedings of the 21st Annual Conference on Learning Theory, COLT 2008, pages 515–516, 2008.
- [13][GKK08b] P. Gopalan, A. T. Kalai, and A. Klivans. Agnostically learning decision trees. In Proceedings of the 40th annual ACM symposium on Theory of computing, STOC 2008, pages 527–536, 2008.DOI
- [14][Han25] X. Han. A new bound for the Fourier-entropy-influence conjecture. Combinatorica, 45, 2025. Article 4.arxiv.org/abs/2312.08271
- [15][Hod17] R. Hod. Improved lower bounds for the Fourier entropy/influence conjecture via lexicographic functions, 2017. arxiv:1711.00762.arxiv.org/abs/1711.00762
- [16][KKL88] J. Kahn, G. Kalai, and Nathan Linial. The influence of variables on Boolean functions. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1988, pages 68–80, 1988.DOI
- [18][KKL+20b] E. Kelman, G. Kindler, N. Lifshitz, D. Minzer, and M. Safra. Towards a proof of the Fourier-entropy conjecture? Geometric and Functional Analysis, 30(4):1097–1138, 2020.arxiv.org/abs/1911.10579
- [19][KLW10] A. Klivans, H. Lee, and A. Wan. Mansour’s conjecture is true for random DNF formulas. In Proceedings of the 23rd Conference on Learning Theory, COLT 2010, pages 368–380, 2010.
- [20][LS07] N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, USA, 2007, pages 699–708. ACM, 2007.
- [21][Man95] Y. Mansour. An n^{O(log log n)} learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences, 50(3):543–550, 1995.
- [22][MW07] A. Montanaro and A. Winter. A lower bound on entanglement-assisted quantum communication complexity. In Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, volume 4596 of Lecture Notes in Computer Science, pages 122–133. Springer, 2007.arxiv.org/abs/quant-ph/0610085
- [23][O’D14] R. O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.arxiv.org/abs/2105.10386
- [24]R. O’Donnell and L-Y. Tan. A composition theorem for the Fourier entropy-influence conjecture. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, pages 780–791, 2013.arxiv.org/abs/1304.1347
- [25]R. O’Donnell, J. Wright, and Y. Zhou. The Fourier entropy-influence conjecture for certain classes of Boolean functions. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, pages 330–341, 2011.DOI
- [26]G. Shalev. On the Fourier Entropy Influence conjecture for extremal classes. arxiv:1806.03646, 2018.arxiv.org/abs/1806.03646
- [27]Y. Shmalo. Fourier entropy of threshold functions and their compositions, October 2026. arXiv:2610.16069, preprint.arxiv.org/abs/2610.16069
- [28]R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, 2008. ToC Library, Graduate Surveys 1.
- [29]A. Wan, J. Wright, and C. Wu. Decision trees, protocols and the entropy-influence conjecture. In Proceedings of the 5th Innovations in Theoretical Computer Science, ITCS 2014, pages 67–80, 2014.DOI