betaFeedback

WorksComputer Science

Fourier Entropy Bounds via Approximations

Abstract

We establish upper bounds on the Shannon entropy H(f^ 2)\mathbb H(\widehat f^{\,2}) of the Fourier distribution of Boolean functions. We prove that H(f^ 2)=O ⁣(log⁡(1+∥f^∥1,1/3)), \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), where ∥f^∥1,1/3\|\widehat f\|_{1,1/3} denotes the minimum spectral norm of a pointwise 1/31/3-approximant to ff. This implies H(f^ 2)=O(R⊕(f))\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f)), where R⊕(f)\mathsf R^\oplus(f) 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 ff as ∑CwC1C\sum_C w_C\mathbf1_C, with nonnegative weights and affine subspaces CC, we prove H(f^ 2)=O ⁣(∑CwC 2−kCkC),kC=codim⁡(C). \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). 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 ff 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 f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\}, Parseval’s identity gives ∑S⊆[n]∣f^(S)∣2=1\sum_{S\subseteq[n]}|\widehat{f}(S)|^{2}=1, so the squared Fourier coefficients define a probability distribution on subsets of [n][n]. Two natural quantities associated with this distribution are its Shannon entropy (H(f^2)\mathbb{H}(\widehat{f}^{2})) and the expected size of a set drawn from it (Inf⁡(f)\operatorname{Inf}(f)):

H(f^2)=∑S⊆[n]∣f^(S)∣2log⁡1∣f^(S)∣2,Inf⁡(f)=∑S⊆[n]∣S∣∣f^(S)∣2.\mathbb{H}(\widehat{f}^{2})=\sum_{S\subseteq[n]}|\widehat{f}(S)|^{2}\log\frac{1}{|\widehat{f}(S)|^{2}},\qquad\operatorname{Inf}(f)=\sum_{S\subseteq[n]}|S||\widehat{f}(S)|^{2}.

The latter quantity is the total influence Inf⁡(f)\operatorname{Inf}(f) of ff, or equivalently, its average sensitivity. Throughout the paper, logarithms are to base two unless otherwise indicated, and 0log⁡(1/0)=00\log(1/0)=0.

Conjecture 1 (Fourier Entropy-Influence Conjecture [9]). There is a universal constant C>0C>0 such that every Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} satisfies

H(f^2)≤C⋅Inf⁡(f).\mathbb{H}(\widehat{f}^{2})\le C\cdot\operatorname{Inf}(f).

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 tt-term DNF is a disjunction of at most tt 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 f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} be computed by a tt-term DNF, where t≥2t\ge2. For every 0<ϵ<10<\epsilon<1, there is a family S⊆2[n]\mathcal{S}\subseteq2^{[n]} such that

∣S∣≤tO(log⁡(1/ϵ))and∑S∈S∣f^(S)∣2≥1−ϵ.|\mathcal{S}|\le t^{O(\log(1/\epsilon))}\qquad\text{and}\qquad\sum_{S\in\mathcal{S}}|\widehat{f}(S)|^{2}\ge1-\epsilon.

By Parseval’s identity, this is a statement about approximation by sparse Fourier polynomials in squared ℓ2\ell_{2} distance. More generally, an entropy bound H(f^2)≤H\mathbb{H}(\widehat{f}^{2})\le H implies that 2O(H/ϵ)2^{O(H/\epsilon)} Fourier coefficients carry at least 1−ϵ1-\epsilon of the weight. Indeed, the coefficients whose squared magnitude is below 2−H/ε2^{-H/\varepsilon} have total weight at most ε\varepsilon. Consequently, FEIC would imply Mansour’s conjecture using the bound Inf⁡(f)=O(log⁡t)\operatorname{Inf}(f) = O(\log t) for tt-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 H(f^2)≤2aUC⁡⊕(f)\mathbb{H}(\widehat{f}^{2}) \leq2\operatorname{aUC}^{\oplus}(f), where aUC⁡⊕(f)\operatorname{aUC}^{\oplus}(f) 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 1+δ1+\delta incur a factor that diverges as δ\delta 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 ∥f^∥1,ε\|\widehat{f}\|_{1,\varepsilon} is the least spectral norm of a polynomial PP satisfying ∣f(x)−P(x)∣≤ε|f(x)-P(x)| \leq\varepsilon at every input. The elementary inequality H(f^2)≤2log⁡∥f^∥1\mathbb{H}(\widehat{f}^{2}) \leq2\log\|\widehat{f}\|_{1} 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

H(f^2)=O(log⁡(1+∥f^∥1,1/3)).(1)\mathbb{H}(\widehat{f}^{2}) = O\left(\log\left(1+\|\widehat{f}\|_{1,1/3}\right)\right). \tag*{(1)}

For any other fixed 0≤ε<10 \leq\varepsilon< 1, the same statement holds with a constant depending only on ε\varepsilon. Thus, the Fourier distribution has small Shannon entropy whenever ff admits an ε\varepsilon-approximating polynomial of small spectral norm, even if the spectral norm of ff itself is much larger.

This yields an entropy bound in terms of bounded-error randomized query complexity. Let R⊕(f)R^{\oplus}(f) denote the minimum worst-case number of parity queries needed to compute ff, with error at most 1/31/3 on every input. Theorem 3.3 states that

H(f2^)=O(R⊕(f)).(2)\mathrm{H}(\widehat{f^2}) = O\left(R^{\oplus}(f)\right). \tag*{(2)}

In particular, H(f2^)=O(R(f))\mathrm{H}(\widehat{f^2}) = O(R(f)) for ordinary randomized query complexity. The expected output of a randomized parity-decision tree is an approximating polynomial whose spectral norm is at most 2R⊕(f)2^{R^{\oplus}(f)}; 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 b∈{0,1}b \in\{0,1\}, consider a partition Ub\mathcal{U}_b of f−1((−1)b)⊆{−1,1}nf^{-1}((-1)^b) \subseteq\{-1,1\}^n into affine subspaces. Its average cost is

∑C∈Ubco-dim⁡(C)2−co-dim⁡(C),\sum_{C\in\mathcal{U}_b} \operatorname{co-dim}(C)2^{-\operatorname{co-dim}(C)},

and minimizing this quantity gives aUC⁡b⊕(f)\operatorname{aUC}^{\oplus}_b(f). The average is taken over the entire uniform input space, with zero cost outside the specified output side. Theorem 4.3 gives

H(f2^)=O(min⁡{aUC⁡0⊕(f),aUC⁡1⊕(f)}).(3)\mathrm{H}(\widehat{f^2}) = O\left(\min\left\{\operatorname{aUC}^{\oplus}_0(f),\operatorname{aUC}^{\oplus}_1(f)\right\}\right). \tag*{(3)}

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 aUC⁡⊕(f)=aUC⁡0⊕(f)+aUC⁡1⊕(f)\operatorname{aUC}^{\oplus}(f)=\operatorname{aUC}^{\oplus}_0(f)+\operatorname{aUC}^{\oplus}_1(f), 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

1−f2=h=∑CwC1C,wC≥0.\frac{1-f}{2}=h=\sum_C w_C1_C,\qquad w_C\geq0.

The average conical junta degree of this representation is

avgdeg⁡cj⊕(h)=∑CwCco-dim⁡(C)2−co-dim⁡(C).\operatorname{avgdeg}^{\oplus}_{\mathrm{cj}}(h)=\sum_C w_C\operatorname{co-dim}(C)2^{-\operatorname{co-dim}(C)}.

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 avgdeg⁡cj⊕(f)\operatorname{avgdeg}_{\mathrm{cj}}^{\oplus}(f). Theorem 4.5 states that

H(f^2)=O(min⁡{avgdeg⁡cj⊕(f),avgdeg⁡cj⊕(−f)}).(4)\mathsf{H}(\widehat{f}^{2}) = O\left(\min\left\{\operatorname{avgdeg}_{\mathrm{cj}}^{\oplus}(f),\operatorname{avgdeg}_{\mathrm{cj}}^{\oplus}(-f)\right\}\right). \tag*{(4)}

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 M∈{−1,1}X×YM \in\{-1,1\}^{X\times Y} be a total sign matrix and let u,vu,v be probability vectors on X,YX,Y. The matrix Au,v=DuMDvA_{u,v}=D_{\sqrt{u}}MD_{\sqrt{v}} has squared Frobenius norm one. Write Hu,v(M)H_{u,v}(M) for the Shannon entropy of its squared singular values. Theorem 5.1 shows that, for every fixed 0≤ε<1/20 \le\varepsilon< 1/2,

Qε∗,cc(M)≥cεHu,v(M),(5)Q_{\varepsilon}^{*,\mathrm{cc}}(M) \ge c_{\varepsilon}H_{u,v}(M), \tag*{(5)}

where arbitrary prior entanglement is allowed and cε>0c_{\varepsilon}>0 is independent of the matrix dimensions and the product weights. For the XOR matrix Mf(x,y)=f(x⊕y)M_f(x,y)=f(x\oplus y), where x⊕yx\oplus y denotes coordinatewise multiplication on {−1,1}n\{-1,1\}^{n}, uniform weights give the Fourier distribution of ff as the squared singular-value distribution. Consequently,

Qε∗,cc(Mf)=Ωε(H(f^2)).Q_{\varepsilon}^{*,\mathrm{cc}}(M_f)=\Omega_{\varepsilon}\left(\mathsf{H}(\widehat{f}^{2})\right).

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 f:{−1,1}n→Cf:\{-1,1\}^{n}\to\mathbb{C} with ∥f∥22≤1\lVert f\rVert_{2}^{2}\le1. Suppose that for every integer j≥1j\ge1 there is an approximant PjP_j such that

∥f−Pj∥22≤2−j,log⁡max⁡{1,∥Pj^∥1}≤CL(j+1)a,\lVert f-P_j\rVert_{2}^{2}\le2^{-j},\qquad\log\max\{1,\lVert\widehat{P_j}\rVert_{1}\}\le CL(j+1)^{a},

where a≥0a\ge0, C>0C>0, and L≥1L\ge1. Then E(f^2)=Oa,C(L)\mathcal{E}(\widehat{f}^{2})=O_{a,C}(L), where E\mathcal{E} 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 f=∑gif = \sum g_i with the nonzero gig_i pairwise orthogonal, set pi=∥gi∥22p_i = \lVert g_i\rVert_2^2 and Li=∥gi^∥1L_i = \lVert\widehat{g_i}\rVert_1. Theorems 4.1 and 4.2 give

∑S∣f^(S)∣r≤∑iLi2−rpir−1(1≤r≤2),\sum_S \lvert\widehat{f}(S)\rvert^r \le\sum_i L_i^{2-r}p_i^{r-1} \qquad(1 \le r \le2),
E(f^2)≤2∑ipilog⁡Lipi.\mathcal{E}(\widehat{f}^2) \le2\sum_i p_i \log\frac{L_i}{p_i}.

The first inequality follows from the Riesz–Thorin interpolation theorem; differentiating at r=2r = 2, where equality holds, yields the second. For the one-sided unambiguous representations, gig_i’s are orthogonal, and hence Theorem 4.2 gives (3). Theorem 4.4 replaces orthogonality by the condition that the Gram matrix Γ=(⟨gi,gj⟩)i,j\Gamma= (\langle g_i,g_j\rangle)_{i,j} has a diagonal majorant Γ⪯diag⁡(ai)\Gamma\preceq\operatorname{diag}(a_i), where ai>0a_i > 0. It gives the same moment bound with aia_i in place of pip_i, and the entropy bound when ∑iai=∥f∥22\sum_i a_i = \lVert f\rVert_2^2. For nonnegative summands in an exact conical representation, the row sums of Γ\Gamma 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-kk decision trees satisfy H(f^2)=O(kInf⁡(f))\mathrm{H}(\widehat{f}^2) = O(k\operatorname{Inf}(f)). Shalev [26] improved the dependence on kk to O(k)O(\sqrt{k}). 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

H(f2^)=O(∑S⊆[n]∣S∣log⁡(∣S∣+1)∣f^(S)∣2).(6)\mathbb{H}(\widehat{f^2}) = O\left(\sum_{S\subseteq[n]} |S|\log(|S|+1)|\widehat{f}(S)|^2\right). \tag*{(6)}

They also obtain bounds on large Fourier coefficients, with applications to learning and sharp thresholds. Han [14] proves the bound,

H(f2^)=O(Inf⁡(f)+∑i=1nInf⁡i(f)log⁡1Inf⁡i(f)).(7)\mathbb{H}(\widehat{f^2}) = O\left(\operatorname{Inf}(f) + \sum_{i=1}^{n}\operatorname{Inf}_i(f)\log\frac{1}{\operatorname{Inf}_i(f)}\right). \tag*{(7)}

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

H(f2^)≤2aUC⊕(f),\mathbb{H}(\widehat{f^2}) \le2\mathrm{aUC}^{\oplus}(f),

where aUC⊕(f)\mathrm{aUC}^{\oplus}(f) 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 UbU_b, write AbA_b for its average cost and db=max⁡C∈Ubco-dim⁡(C)d_b=\max_{C\in U_b}\operatorname{co-dim}(C). The one-sided bound in [1 Theorem 1.7] is

H(f2^)≤2(Ab+Pr⁡[f≠(−1)b]db).\mathbb{H}(\widehat{f^2}) \le2\left(A_b+\Pr[f\ne(-1)^b]d_b\right).

Our bound is O(Ab)O(A_b), with no dependence on dbd_b. 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 Hu,v(M)/2H_{u,v}(M)/2 and a bounded-error bound of Ω(Hu,v(M)/log⁡n)\Omega(H_{u,v}(M)/\log n) for nn-bit inputs, allowing product weights and prior entanglement. For uniform N×NN \times N sign matrices, Linial and Shraibman [20 Theorem 30] obtained

Q1/3∗,cc(M)≥Ω(E1+log⁡((log⁡N)/E)),E=Hu,v(M)>0.Q^{*,\mathrm{cc}}_{1/3}(M) \ge\Omega\left(\frac{E}{1+\log((\log N)/E)}\right), \qquad E=H_{u,v}(M)>0.

Our bound (5) removes this denominator. The improvement is relevant when EE is small relative to log⁡N\log N. 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 {−1,1}n\{-1,1\}^{n} to C\mathbb{C} equipped with the inner product defined as

⟨f,g⟩:=Ex[f(x)‾g(x)]=12n∑x∈{−1,1}nf(x)‾g(x).\langle f,g\rangle:= \mathbb{E}_{x}[\overline{f(x)}g(x)] = \frac{1}{2^{n}}\sum_{x\in\{-1,1\}^{n}}\overline{f(x)}g(x).

For S⊆[n]S \subseteq[n], the character function χS:{−1,1}n→{−1,1}\chi_{S}:\{-1,1\}^{n}\to\{-1,1\} is defined as χS(x):=∏i∈Sxi\chi_{S}(x):=\prod_{i\in S}x_{i}. Then the set of character functions {χS}S⊆[n]\{\chi_{S}\}_{S\subseteq[n]} forms an orthonormal basis for the space of all complex-valued functions on {−1,1}n\{-1,1\}^{n}. Hence, every complex-valued function f:{−1,1}n→Cf:\{-1,1\}^{n}\to\mathbb{C} has a unique Fourier expansion

f(x)=∑S⊆[n]f^(S)χS(x).f(x)=\sum_{S\subseteq[n]}\widehat{f}(S)\chi_{S}(x).

The degree of ff, denoted deg⁡(f)\deg(f), is defined as max⁡{∣S∣:f^(S)≠0}\max\{ |S|:\widehat{f}(S)\ne0\}. The spectral norm ∥f^∥1\|\widehat{f}\|_{1} of ff is defined to be ∑S∣f^(S)∣\sum_{S}|\widehat{f}(S)|. The Fourier weight of a function ff on a set S\mathcal{S} of coefficients is defined as ∑S∈S∣f^(S)∣2\sum_{S\in\mathcal{S}}|\widehat{f}(S)|^{2}. For 0≤ε<10\le\varepsilon<1, the ε\varepsilon-approximate spectral norm ∥f^∥1,ε\|\widehat{f}\|_{1,\varepsilon} of a Boolean function ff is defined as

∥f^∥1,ε=min⁡{∑S∣p^(S)∣:∣p(x)−f(x)∣≤ε for every x∈{−1,1}n}.\|\widehat{f}\|_{1,\varepsilon}=\min\left\{\sum_{S}|\widehat{p}(S)|: |p(x)-f(x)|\le\varepsilon\text{ for every }x\in\{-1,1\}^{n}\right\}.

We will use f^:{−1,1}n→C\widehat{f}:\{-1,1\}^{n}\to\mathbb{C} to denote the function that maps SS to its Fourier coefficient f^(S)\widehat{f}(S). We note a well-known fact that follows from the orthonormality of the character functions.

Fact 2.1 (Plancherel’s Theorem). For any f,g:{−1,1}n→Cf,g:\{-1,1\}^{n}\to\mathbb{C},

⟨f,g⟩=Ex[f(x)‾g(x)]=∑S⊆[n]f^(S)‾g^(S)=⟨f^,g^⟩.\langle f,g\rangle=\mathbb{E}_{x}[\overline{f(x)}g(x)]=\sum_{S\subseteq[n]}\overline{\widehat{f}(S)}\widehat{g}(S)=\langle\widehat{f},\widehat{g}\rangle.

In particular, if f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} is Boolean-valued and g=fg=f, we have Parseval’s Identity ∑S∣f^(S)∣2=E[∣f(x)∣2]\sum_{S}|\widehat{f}(S)|^{2}=\mathbb{E}[|f(x)|^{2}], which in turn equals 11. Hence ∑S∣f^(S)∣2=1\sum_{S}|\widehat{f}(S)|^{2}=1 and we can view {∣f^(S)∣2}S\{|\widehat{f}(S)|^{2}\}_{S} as a probability distribution, which allows us to discuss the Fourier entropy and min-entropy of the distribution {∣f^(S)∣2}S\{|\widehat{f}(S)|^{2}\}_{S}, defined as

Definition 2.2. For a Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\}, its Fourier entropy (denoted H(f^2)\mathbb{H}(\widehat{f}^{2})) and min-entropy (denoted H∞(f^2)\mathbb{H}_{\infty}(\widehat{f}^{2})) are

H(f^2):=∑S⊆[n]∣f^(S)∣2log⁡1∣f^(S)∣2,andH∞(f^2):=min⁡S⊆[n]:f^(S)≠0{log⁡1∣f^(S)∣2}.\mathbb{H}(\widehat{f}^{2}):=\sum_{S\subseteq[n]}|\widehat{f}(S)|^{2}\log\frac{1}{|\widehat{f}(S)|^{2}},\qquad\text{and}\qquad\mathbb{H}_{\infty}(\widehat{f}^{2}):=\min_{\substack{S\subseteq[n]:\\ \widehat{f}(S)\ne0}}\left\{\log\frac{1}{|\widehat{f}(S)|^{2}}\right\}.

Similarly, we can also define the Rényi Fourier entropy.

Definition 2.3 (Rényi Fourier entropy). For f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\}, α≥0\alpha\ge0 and α≠1\alpha\ne1, the Rényi Fourier entropy of ff of order α\alpha is defined as

Hα(f^2):=11−αlog⁡(∑S⊆[n]∣f^(S)∣2α).\mathbb{H}_{\alpha}(\widehat{f}^{2}):=\frac{1}{1-\alpha}\log\left(\sum_{S\subseteq[n]}|\widehat{f}(S)|^{2\alpha}\right).

It is known that in the limit as α→1\alpha\to1, Hα(f^2)\mathbb{H}_{\alpha}(\widehat{f}^{2}) is the (Shannon) Fourier entropy H(f^2)\mathbb{H}(\widehat{f}^{2}) (see [7 Chapter 17, Section 8]) and when α→∞\alpha\to\infty, observe that Hα(f^2)\mathbb{H}_{\alpha}(\widehat{f}^{2}) converges to H∞(f^2)\mathbb{H}_{\infty}(\widehat{f}^{2}). It is easily seen that

H∞(f^2)≤H1(f^2)≤H12(f^2)≤H0(f^2).\mathbb{H}_{\infty}(\widehat{f}^{2})\le\mathbb{H}_{1}(\widehat{f}^{2})\le\mathbb{H}_{\frac{1}{2}}(\widehat{f}^{2})\le\mathbb{H}_{0}(\widehat{f}^{2}).

For an arbitrary function g:{−1,1}n→Cg:\{-1,1\}^{n}\to\mathbb{C}, we will define

E(g^2):=∑S⊆[n]∣g^(S)∣2log⁡1∣g^(S)∣2.(8)\mathcal{E}(\widehat{g}^{2}):=\sum_{S\subseteq[n]}|\widehat{g}(S)|^{2}\log\frac{1}{|\widehat{g}(S)|^{2}}. \tag*{(8)}

Note that ∑S∣g^(S)∣2\sum_{S}|\widehat{g}(S)|^2 need not equal 1. In the special case of Boolean functions f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} we have the following relationship.

Lemma 2.4. Let f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} be any Boolean function and g:=(1+f)/2g:=(1+f)/2 (or, (1−f)/2(1-f)/2). Then,

H(f^2)=4E(g^2)−φ(p)≤4E(g^2),(9)\mathbb{H}(\widehat{f}^{2})=4\mathcal{E}(\widehat{g}^{2})-\varphi(p)\leq4\mathcal{E}(\widehat{g}^{2}), \tag*{(9)}

where p=E[g]=Pr⁡[g=1]p=\mathbb{E}[g]=\Pr[g=1] and φ(p)=4p2log⁡1p2+8p(1−p)−(1−2p)2log⁡1(1−2p)2\varphi(p)=4p^2\log\frac{1}{p^2}+8p(1-p)-(1-2p)^2\log\frac{1}{(1-2p)^2}. Moreover, φ(p)≥0\varphi(p)\geq0 for all 0≤p≤10\leq p\leq1.

For f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}, the influence of a coordinate i∈[n]i\in[n], denoted Inf⁡i(f)\operatorname{Inf}_i(f), is defined as

Inf⁡i(f)=Pr⁡x∈{−1,1}n[f(x)≠f(x(i))]=Ex[(f(x)−f(x(i))2)2].\operatorname{Inf}_i(f)=\Pr_{x\in\{-1,1\}^n}\left[f(x)\ne f(x^{(i)})\right]=\mathbb{E}_x\left[\left(\frac{f(x)-f(x^{(i)})}{2}\right)^2\right].

where the probability and expectation is taken according to the uniform distribution on {−1,1}n\{-1,1\}^n and x(i)x^{(i)} is xx with the ii-th bit flipped. The total influence of ff, denoted Inf⁡(f)\operatorname{Inf}(f), is

Inf⁡(f)=∑i∈[n]Inf⁡i(f).\operatorname{Inf}(f)=\sum_{i\in[n]}\operatorname{Inf}_i(f).

In terms of the Fourier coefficients of ff, it can be shown, e.g., [16], that Inf⁡i(f)=∑S∋if^(S)2\operatorname{Inf}_i(f)=\sum_{S\ni i}\widehat{f}(S)^2, and therefore

Inf⁡(f)=∑S⊆[n]∣S∣f^(S)2.\operatorname{Inf}(f)=\sum_{S\subseteq[n]}|S|\widehat{f}(S)^2.

The variance of a real-valued function ff is given by Var⁡(f):=∑S≠∅f^(S)2=1−∣f^(∅)∣2\operatorname{Var}(f):=\sum_{S\ne\emptyset}\widehat{f}(S)^2=1-|\widehat{f}(\emptyset)|^2. It easily follows that Var⁡(f)≤Inf⁡(f)\operatorname{Var}(f)\leq\operatorname{Inf}(f). We now introduce some basic complexity measures of Boolean functions which we use often, referring to [4] for more.

Sensitivity For x∈{−1,1}nx\in\{-1,1\}^n, the sensitivity of ff at xx, denoted sf(x)s_f(x), is defined to be the number of neighbors yy of xx in the Boolean hypercube (i.e., yy is obtained by flipping exactly one bit of xx) such that f(y)≠f(x)f(y)\ne f(x). The sensitivity s(f)s(f) of ff is max⁡x{sf(x)}\max_x\{s_f(x)\}. The average sensitivity as⁡(f)\operatorname{as}(f) of ff is defined to be Ex[sf(x)]\mathbb{E}_x[s_f(x)]. By the linearity of expectation observe that

Ex[sf(x)]=∑i=1nPr⁡x[f(x)≠f(x(i))]=∑i=1nInf⁡i(f)=Inf⁡(f),\mathbb{E}_x[s_f(x)]=\sum_{i=1}^{n}\Pr_x\left[f(x)\ne f(x^{(i)})\right]=\sum_{i=1}^{n}\operatorname{Inf}_i(f)=\operatorname{Inf}(f),

so the average sensitivity of ff equals the total influence of ff. As a result, the FEI conjecture asks if H(f^2)≤C⋅as⁡(f)\mathbb{H}(\widehat{f}^{2})\leq C\cdot\operatorname{as}(f) for every Boolean function ff.

Certificate complexity For x∈{−1,1}nx \in\{-1,1\}^{n}, the certificate complexity of ff at xx, denoted C(f,x)C(f,x), is the minimum number of bits in xx that needs to be fixed to ensure that the value of ff is constant. The certificate complexity C(f)C(f) of ff is max⁡x{C(f,x)}\max_{x}\{C(f,x)\}. The minimum certificate complexity of ff is Cmin⁡(f)=min⁡x{C(f,x)}C_{\min}(f) = \min_{x}\{C(f,x)\}. The 0-certificate complexity C0(f)C^{0}(f) of ff is max⁡x:f(x)=1{C(f,x)}\max_{x:f(x)=1}\{C(f,x)\}. Similarly, the 1-certificate complexity C1(f)C^{1}(f) of ff is max⁡x:f(x)=−1{C1(f,x)}\max_{x:f(x)=-1}\{C^{1}(f,x)\}. Observe that for every x∈{−1,1}nx \in\{-1,1\}^{n}, s(f,x)≤C(f,x)s(f,x) \le C(f,x). This gives s(f)≤C(f)s(f) \le C(f) and as⁡(f)≤aC⁡(f)\operatorname{as}(f) \le\operatorname{aC}(f) where aC⁡(f)\operatorname{aC}(f) denotes the average certificate complexity of ff. As before, the average is taken with respect to the uniform distribution on {−1,1}n\{-1,1\}^{n}.

Parity-certificate complexity Analogously, we define the parity-certificate complexity C⊕(f,x)C^{\oplus}(f,x) of ff at xx as the minimum number of parities on the input variables one has to fix in order to fix the value of ff at xx, i.e.,

C⊕(f,x):=min⁡{co-dim⁡(H)∣H is an affine subspace on which f is constant and x∈H}.C^{\oplus}(f,x) := \min\{\operatorname{co-dim}(H) \mid H \text{ is an affine subspace on which } f \text{ is constant and } x \in H\}.

where co-dim⁡(H)\operatorname{co-dim}(H) is the co-dimension of the affine subspace HH. It is easily seen that C⊕(f,x)≤C(f,x)C^{\oplus}(f,x) \le C(f,x). We also define C⊕(f):=max⁡x{C⊕(f,x)}C^{\oplus}(f) := \max_{x}\{C^{\oplus}(f,x)\}, and Cmin⁡⊕(f):=min⁡x{C⊕(f,x)}C_{\min}^{\oplus}(f) := \min_{x}\{C^{\oplus}(f,x)\}.

Unambiguous certificate complexity We now define the unambiguous certificate complexity of ff. Let τ:[n]→{−1,1,∗}\tau: [n] \to\{-1,1,*\} be a partial assignment. We refer to

Sτ={x∈{−1,1}n:xi=τ(i) for every i∈[n]∖τ−1(∗)}S_{\tau} = \{x \in\{-1,1\}^{n} : x_i = \tau(i) \text{ for every } i \in[n] \setminus\tau^{-1}(*)\}

as the subcube generated by τ\tau. We call C⊆{−1,1}nC \subseteq\{-1,1\}^{n} a subcube of {−1,1}n\{-1,1\}^{n} if there exists a partial assignment τ\tau such that C=SτC = S_{\tau} and the co-dimension of CC is the number of bits fixed by τ\tau, i.e., co-dim⁡(C)=∣{i∈[n]:τ(i)≠∗}∣\operatorname{co-dim}(C) = |\{i \in[n] : \tau(i) \ne*\}|. A set of subcubes C={C1,…,Cm}\mathcal{C} = \{C_{1},\ldots,C_{m}\} partitions {−1,1}n\{-1,1\}^{n} if the subcubes are disjoint and they cover {−1,1}n\{-1,1\}^{n}, i.e., Ci∩Cj=∅C_i \cap C_j = \varnothing for i≠ji \ne j and ⋃iCi={−1,1}n\bigcup_i C_i = \{-1,1\}^{n}.

An unambiguous certificate U={C1,…,Cm}\mathcal{U} = \{C_{1},\ldots,C_{m}\}, also referred to as a subcube partition, is a set of subcubes partitioning {−1,1}n\{-1,1\}^{n}. We say U\mathcal{U} computes a Boolean function f:{−1,1}n→{−1,1}f : \{-1,1\}^{n} \to\{-1,1\} if ff is constant on each CiC_i (i.e., f(x)f(x) is the same for all x∈Cix \in C_i). For an unambiguous certificate U\mathcal{U}, the unambiguous certificate complexity UC⁡(U,x)\operatorname{UC}(\mathcal{U},x) on input xx equals co-dim⁡(Ci)\operatorname{co-dim}(C_i) for the CiC_i satisfying x∈Cix \in C_i. Define the average unambiguous certificate complexity of ff with respect to U\mathcal{U} as

aUC⁡(f,U):=Ex[UC⁡(U,x)].\operatorname{aUC}(f,\mathcal{U}) := \mathbb{E}_{x}[\operatorname{UC}(\mathcal{U},x)].

Then, the average unambiguous certificate complexity of ff is defined as

aUC⁡(f):=min⁡UaUC⁡(f,U).\operatorname{aUC}(f) := \min_{\mathcal{U}} \operatorname{aUC}(f,\mathcal{U}).

where the minimization is over all unambiguous certificates for ff. We also define the one-sided version of these measures. Let U=U0⊔U1\mathcal{U}=\mathcal{U}_0\sqcup\mathcal{U}_1 be such that, for b∈{0,1}b\in\{0,1\}, Ub\mathcal{U}_b is an unambiguous bb-certificate, i.e., Ub\mathcal{U}_b is a subcube partition of f−1((−1)b)f^{-1}((-1)^b). Then, define aUC⁡(f,Ub)=(1/2n)∑x∈UbUC⁡(Ub,x)\operatorname{aUC}(f,\mathcal{U}_b)=(1/2^n)\sum_{x\in\mathcal{U}_b}\operatorname{UC}(\mathcal{U}_b,x) and note that aUC⁡(f,U)=aUC⁡(f,U0)+aUC⁡(f,U1)\operatorname{aUC}(f,\mathcal{U})=\operatorname{aUC}(f,\mathcal{U}_0)+\operatorname{aUC}(f,\mathcal{U}_1). We therefore define the average unambiguous bb-certificate complexity of ff as

aUC⁡b(f):=min⁡UbaUC⁡(f,Ub),\operatorname{aUC}_b(f):=\min_{\mathcal{U}_b}\operatorname{aUC}(f,\mathcal{U}_b),

where the minimization is over all unambiguous bb-certificates Ub\mathcal{U}_b for ff. Observe that aUC⁡(f)=aUC⁡0(f)+aUC⁡1(f)\operatorname{aUC}(f)=\operatorname{aUC}_0(f)+\operatorname{aUC}_1(f). Finally, the unambiguous certificate complexity of ff is

UC⁡(f):=min⁡Umax⁡xUC⁡(U,x).\operatorname{UC}(f):=\min_{\mathcal{U}}\max_x\operatorname{UC}(\mathcal{U},x).

Note that since unambiguous certificates are more restricted than general certificates, we have C(f)≤UC⁡(f)C(f)\leq\operatorname{UC}(f).

An unambiguous ⊕\oplus-certificate U={C1,…,Cm}\mathcal{U}=\{C_1,\ldots,C_m\} for ff is defined to be a collection of monochromatic affine subspaces that together partition the space {−1,1}n\{-1,1\}^n. It is easily seen that a subcube is also an affine subspace. Analogously, for an unambiguous ⊕\oplus-certificate U\mathcal{U}, on an input xx, UC⁡⊕(U,x):=co-dim⁡(Ci)\operatorname{UC}^{\oplus}(\mathcal{U},x):=\operatorname{co-dim}(C_i) for the CiC_i satisfying x∈Cix\in C_i, and aUC⁡⊕(f,U):=Ex[UC⁡⊕(U,x)]\operatorname{aUC}^{\oplus}(f,\mathcal{U}):=\mathbb{E}_x[\operatorname{UC}^{\oplus}(\mathcal{U},x)]. Similarly, we define aUC⁡⊕(f)\operatorname{aUC}^{\oplus}(f), aUC⁡0⊕(f)\operatorname{aUC}^{\oplus}_0(f), aUC⁡1⊕(f)\operatorname{aUC}^{\oplus}_1(f), and UC⁡⊕(f)\operatorname{UC}^{\oplus}(f).

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 (−1)(-1)-input, exactly one of the conjunctions outputs −1-1. Note that an unambiguous DNF for ff is equivalently an unambiguous 1-certificate for ff.

Approximate degree The ε\varepsilon-approximate degree of f:{−1,1}n→Rf:\{-1,1\}^n\to\mathbb{R}, denoted deg⁡ε(f)\deg_{\varepsilon}(f), is defined to be the minimum degree among all multilinear real polynomials pp such that ∣f(x)−p(x)∣≤ε\lvert f(x)-p(x)\rvert\leq\varepsilon for all x∈{−1,1}nx\in\{-1,1\}^n. Usually ε\varepsilon is chosen to be 1/31/3, but it can be chosen to be any constant in (0,1)(0,1), without significantly changing the model.

Deterministic decision trees A deterministic decision tree for f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} is a rooted binary tree where each node is labelled by i∈[n]i\in[n] and the leaves are labelled with an output bit {−1,1}\{-1,1\}. On input x∈{−1,1}nx\in\{-1,1\}^n, the tree proceeds at a node with label ii by evaluating the bit xix_i and continuing with the subtree corresponding to the value of xix_i. Once a leaf is reached, the tree outputs a bit. We say that a deterministic decision tree computes ff if for all x∈{−1,1}nx\in\{-1,1\}^n its output equals f(x)f(x).

A parity-decision tree for ff is similar to a deterministic decision tree, except that each node in the tree is labelled by a subset S⊆[n]S \subseteq[n]. On input x∈{−1,1}nx \in\{-1,1\}^{n}, the tree proceeds at a node with label SS by evaluating the parity of the bits xix_i for i∈Si \in S and continues with the subtree corresponding to the value of ⨁i∈Sxi\bigoplus_{i\in S}x_i. Note that if the subsets at each node have size ∣S∣=1|S| = 1, then we get the standard deterministic decision tree model.

Randomized decision trees A randomized decision tree for ff is a probability distribution μ\mu over deterministic decision trees for ff. On input xx, a decision tree is chosen according to μ\mu, which is then evaluated on xx. The complexity of the randomized tree is the largest depth among all deterministic trees with non-zero probability of being sampled according to μ\mu. One can similarly define a randomized parity-decision tree as a probability distribution over deterministic parity-decision trees for ff.

We say that a randomized decision tree computes ff with bounded-error if for all x∈{−1,1}nx \in\{-1,1\}^{n} its output equals f(x)f(x) with probability at least 2/32/3. R(f)R(f) (respectively, R⊕(f)R^{\oplus}(f)) denotes the complexity of the optimal randomized (respectively, parity) decision tree that computes ff with bounded-error, i.e., errs with probability at most 1/31/3.

Conical Juntas Let h=∑CwCCh = \sum_C w_C C, a conical junta, be a weighted sum over conjunctions CC of literals with weights wC≥0w_C \ge0. We say that a Boolean function f:{−1,1}n→{−1,1}f : \{-1,1\}^{n} \to\{-1,1\} is represented by a conical junta hh if g=(1−f)/2=hg = (1-f)/2 = h. More generally, we will consider (non-negative) weighted sum over affine subspaces. We define the average conical junta degree of hh, denoted avgdeg⁡cj⊕(h)\operatorname{avgdeg}^{\oplus}_{\mathrm{cj}}(h), equals ∑CwCco-dim⁡(C)2−co-dim⁡(C)\sum_C w_C\operatorname{co-dim}(C)2^{-\operatorname{co-dim}(C)}. Then, the average conical junta degree of ff is avgdeg⁡cj⊕(f):=min⁡h a conical juntaavgdeg⁡cj⊕(h)\operatorname{avgdeg}^{\oplus}_{\mathrm{cj}}(f) := \min_{h\text{ a conical junta}}\operatorname{avgdeg}^{\oplus}_{\mathrm{cj}}(h) the minimum average conical junta degree over all conical junta representations hh. Similar measures were studied in [11].

Theorem 2.5 (The Reisz-Thorin Interpolation Theorem [10 Theorem 6.27]). Let II and JJ be non-empty finite sets. Further let T:CI→CJT : \mathbb{C}^{I} \to\mathbb{C}^{J} be a linear map, and νi>0\nu_i > 0 for i∈Ii \in I be such that for every u∈CIu \in\mathbb{C}^{I},

∥Tu∥1≤∑i∈Iνi∣ui∣,and∥Tu∥22≤∑i∈Iνi∣ui∣2.(10)\|Tu\|_1 \le\sum_{i\in I}\nu_i|u_i|,\qquad\text{and}\qquad\|Tu\|_2^2 \le\sum_{i\in I}\nu_i|u_i|^2. \tag*{(10)}

Then, for every 1≤r≤21 \le r \le2,

∥Tu∥rr=∑j∈J∣(Tu)j∣r≤∑i∈Iνi∣ui∣r.(11)\|Tu\|_r^r = \sum_{j\in J}|(Tu)_j|^r \le\sum_{i\in I}\nu_i|u_i|^r. \tag*{(11)}

Approximants

Theorem 3.1. Let f:{−1,1}n→Cf:\{-1,1\}^{n}\to\mathbb{C} with ∥f∥22≤1\|f\|_{2}^{2}\le1. Suppose that a≥0a\ge0, C>0C>0, L≥1L\ge1, and for any integer j≥1j\ge1, there is a function Pj:{−1,1}n→CP_j:\{-1,1\}^{n}\to\mathbb{C} such that

∥f−Pj∥22≤2−jandlog⁡max⁡{1,∥Pj^∥1}≤CL(j+1)a.(12)\|f-P_j\|_{2}^{2}\le2^{-j}\qquad\text{and}\qquad\log\max\{1,\|\widehat{P_j}\|_{1}\}\le CL(j+1)^{a}. \tag*{(12)}

Then,

E(f^2)≤6+4CKaL=Oa,C(L),(13)\mathcal{E}(\widehat{f}^{2})\le6+4CK_aL=O_{a,C}(L), \tag*{(13)}

where Ka=∑j≥12−j(j+3)a=O(2aa!)K_a=\sum_{j\ge1}2^{-j}(j+3)^{a}=O(2^{a}a!).

Proof. For each j≥1j\ge1, define the following set of good monomials

Gj={S∣f^(S)≠0, ∣f^(S)−P^j+2(S)∣≤∣f^(S)∣/2}.(14)G_j=\left\{S\mid\widehat{f}(S)\ne0,\ \left|\widehat{f}(S)-\widehat{P}_{j+2}(S)\right|\le\left|\widehat{f}(S)\right|/2\right\}. \tag*{(14)}

Using GjG_j's we partition the set of non-zero Fourier coefficients as follows: for each j≥1j\ge1,

Tj:=Gj∖⋃k<jGk.(15)T_j:=G_j\setminus\bigcup_{k<j}G_k. \tag*{(15)}

Since ∥f−Pj∥22→0\|f-P_j\|_{2}^{2}\to0, as j→∞j\to\infty, every fixed non-zero coefficient eventually becomes good, and thus TjT_j's partitions the set of non-zero Fourier coefficients of ff.

Let us define the Fourier weight μj\mu_j on the part TjT_j, i.e., μj:=∑S∈Tj∣f^(S)∣2\mu_j:=\sum_{S\in T_j}|\widehat{f}(S)|^{2}. Also define Bj:=max⁡{1,∥P^j+2∥1}B_j:=\max\{1,\|\widehat{P}_{j+2}\|_{1}\} and ρ:=∥f∥22≤1\rho:=\|f\|_{2}^{2}\le1. From the definitions it follows that ∑j≥1μj=ρ\sum_{j\ge1}\mu_j=\rho and

∑k>jμk≤∑S∉Gj∣f^(S)∣2≤∑S∉Gj4∣f^(S)−P^j+2(S)∣2≤4∥f−Pj+2∥22≤2−j,(16)\sum_{k>j}\mu_k\le\sum_{S\notin G_j}|\widehat{f}(S)|^{2}\le\sum_{S\notin G_j}4\left|\widehat{f}(S)-\widehat{P}_{j+2}(S)\right|^{2}\le4\|f-P_{j+2}\|_{2}^{2}\le2^{-j}, \tag*{(16)}

where the last inequality follows from (12). Further, we have

μj=∑S∈Tj∣f^(S)∣2≤∑S∉Gj−1∣f^(S)∣2≤2−(j−1).(17)\mu_j=\sum_{S\in T_j}|\widehat{f}(S)|^{2}\le\sum_{S\notin G_{j-1}}|\widehat{f}(S)|^{2}\le2^{-(j-1)}. \tag*{(17)}

We also have for S∈TjS\in T_j, ∣f^(S)∣≤2∣P^j+2(S)∣|\widehat{f}(S)|\le2|\widehat{P}_{j+2}(S)|, and therefore, ∑S∈Tj∣f^(S)∣≤2Bj\sum_{S\in T_j}|\widehat{f}(S)|\le2B_j. We can thus bound E(f^2)\mathcal{E}(\widehat{f}^{2}) as follows

E(f^2)=∑j≥1Tj≠∅∑S∈Tj∣f^(S)∣2log⁡1∣f^(S)∣2=∑j≥1Tj≠∅2μj∑S∈Tj∣f^(S)∣2μjlog⁡1∣f^(S)∣,≤∑j:Tj≠∅2μjlog⁡(∑S∈Tj∣f^(S)∣μj)≤2∑j:Tj≠∅μjlog⁡(2Bjμj),=2∑jμjlog⁡2μj+2∑jμjlog⁡Bj,=2(ρ+∑jjμj+∑jμjlog⁡2−jμj)+2∑jμjlog⁡Bj.(18)\begin{aligned} \mathcal{E}(\widehat{f}^{2}) &= \sum_{\substack{j\geq1\\ T_j\ne\emptyset}}\sum_{S\in T_j}|\widehat{f}(S)|^2\log\frac{1}{|\widehat{f}(S)|^2} = \sum_{\substack{j\geq1\\ T_j\ne\emptyset}}2\mu_j\sum_{S\in T_j}\frac{|\widehat{f}(S)|^2}{\mu_j}\log\frac{1}{|\widehat{f}(S)|},\\ &\leq\sum_{\substack{j:T_j\ne\emptyset}}2\mu_j\log\left(\sum_{S\in T_j}\frac{|\widehat{f}(S)|}{\mu_j}\right) \leq2\sum_{j:T_j\ne\emptyset}\mu_j\log\left(\frac{2B_j}{\mu_j}\right),\\ &=2\sum_j\mu_j\log\frac{2}{\mu_j}+2\sum_j\mu_j\log B_j,\\ &=2\left(\rho+\sum_jj\mu_j+\sum_j\mu_j\log\frac{2^{-j}}{\mu_j}\right)+2\sum_j\mu_j\log B_j. \tag*{(18)} \end{aligned}

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

∑j≥1jμj=∑j≥1μj+∑j≥1∑k>jμk≤ρ+1,\sum_{j\geq1}j\mu_j=\sum_{j\geq1}\mu_j+\sum_{j\geq1}\sum_{k>j}\mu_k\leq\rho+1,
∑j≥1μjlog⁡2−jμj=ρ∑j≥1μjρlog⁡2−jμj≤ρlog⁡(∑j≥1μj>02−jρ)≤ρlog⁡1ρ≤2(1−ρ),\sum_{j\geq1}\mu_j\log\frac{2^{-j}}{\mu_j} =\rho\sum_{j\geq1}\frac{\mu_j}{\rho}\log\frac{2^{-j}}{\mu_j} \leq\rho\log\left(\sum_{\substack{j\geq1\\ \mu_j>0}}\frac{2^{-j}}{\rho}\right) \leq\rho\log\frac{1}{\rho}\leq2(1-\rho),

and

∑j≥1μjlog⁡Bj≤CL∑j≥1μj(j+3)a≤2CL∑j≥12−j(j+3)a=2CLKa,\sum_{j\geq1}\mu_j\log B_j\leq CL\sum_{j\geq1}\mu_j(j+3)^a\leq2CL\sum_{j\geq1}2^{-j}(j+3)^a=2CLKa,

where we used equations (16), (17), (12) and the Jensen’s inequality to simplify. Substituting them back in (18) we obtain

E(f^2)≤6+4CLKa.\mathcal{E}(\widehat{f}^{2})\leq6+4CLK_a.

Proof.

As an application we show that Fourier-entropy is bounded by the logarithm of ε\varepsilon-approximate spectral norm.

Theorem 3.2. Let f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} be a Boolean function. Then, for ε>0\varepsilon>0, H(f)=O(log⁡(1+∥f^∥1,ε))\mathbb{H}(f)=O(\log(1+\|\widehat{f}\|_{1,\varepsilon})).

Proof. Without loss of generality, assume ε=1/3\varepsilon=1/3. Let P′P' be a 1/31/3-approximating polynomial for ff, and let P:=3P′/4P:=3P'/4. Let Maj⁡t\operatorname{Maj}_t be the Majority function on tt variables. Then, define Pt:=Maj⁡t(P,…,P)P_t:=\operatorname{Maj}_t(P,\ldots,P) and B:=∥P^∥1≤∥P′^∥1B:=\|\widehat{P}\|_1\leq\|\widehat{P'}\|_1. It is well known that the following facts holds:

  1. ∥f−Pt∥∞≤2e−t/8\|f-P_t\|_\infty\leq2e^{-t/8}, and hence ∥f−Pt∥22≤4e−t/4\|f-P_t\|_2^2\leq4e^{-t/4}, while

  1. ∥P^t∥1≤(1+B2)t/2\|\widehat{P}_t\|_1 \le(1+B^2)^{t/2}.

For each j≥1j \ge1, define the approximant Qj:=P4j+8Q_j := P_{4j+8}. We, therefore, have

∥f−Qj∥22≤2−j,andlog⁡max⁡{1,∥Q^j∥1}≤O(jlog⁡(1+B)).\|f-Q_j\|_2^2 \le2^{-j}, \qquad\text{and} \qquad\log\max\{1,\|\widehat{Q}_j\|_1\} \le O(j\log(1+B)).

It, thus follows from Theorem 3.1,

H(f2^)=O(log⁡(1+B)),\mathbb{H}(\widehat{f^2})=O(\log(1+B)),

and therefore,

H(f2^)=O(log⁡(1+∥f^∥1,1/3)).\mathbb{H}(\widehat{f^2})=O(\log(1+\|\widehat{f}\|_{1,1/3})).

The second equality follows since P′P' is an arbitrary 1/31/3-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 f:{−1,1}n→{−1,1}f:\{-1,1\}^n \to\{-1,1\} be a Boolean function and R⊕(f)R^{\oplus}(f) be the randomized parity-decision tree complexity of ff with error at most 1/31/3. Then, H(f2^)=O(R⊕(f))\mathbb{H}(\widehat{f^2})=O(R^{\oplus}(f)).

Proof. Let T\mathcal{T} be a randomized ⊕\oplus-decision tree computing ff. That is, it is a distribution μ\mu on deterministic ⊕\oplus-decision trees T1,…,TtT_1,\ldots,T_t such that for each input xx, Pr⁡T∼μ[T(x)=f(x)]≥2/3\Pr_{T\sim\mu}[T(x)=f(x)]\ge2/3.

Then, consider the polynomial P(x)=∑i=1tμ(Ti)pi(x)P(x)=\sum_{i=1}^{t}\mu(T_i)p_i(x), where pi(x)p_i(x) are polynomials representing TiT_i exactly. Therefore, for each input xx, P(x)=ET∼μ[T(x)]P(x)=\mathbb{E}_{T\sim\mu}[T(x)] and thus ∣f(x)−P(x)∣≤2/3|f(x)-P(x)|\le2/3. Hence, PP is a 2/32/3-approximating polynomial for ff. Furthermore, ∥P^∥1≤2R⊕(f)\|\widehat{P}\|_1\le2^{R^{\oplus}(f)}. The bound now follows from an application of Theorem 3.2.

Moment Inequality

Theorem 4.1. Let f:{−1,1}n→Cf:\{-1,1\}^n\to\mathbb{C} and f=∑i=1mgif=\sum_{i=1}^{m}g_i where the non-zero functions gi:{−1,1}n→Cg_i:\{-1,1\}^n\to\mathbb{C} are pairwise orthogonal. Define pi:=∥gi∥22p_i:=\|g_i\|_2^2 and Li:=∥gi^∥1L_i:=\|\widehat{g_i}\|_1. Then, for every 1≤r≤21\le r\le2,

∑S⊆[n]∣f^(S)∣r≤∑i=1mLi2−rpir−1.(19)\sum_{S\subseteq[n]}|\widehat{f}(S)|^r\le\sum_{i=1}^{m}L_i^{2-r}p_i^{r-1}. \tag*{(19)}

Equality holds at r=2r=2.

Proof. Define νi=Li2/pi\nu_i=L_i^2/p_i for i∈[m]i\in[m], and the linear operator T:Cm→C2nT:\mathbb{C}^m\to\mathbb{C}^{2^n} by

Tu=∑i=1mLipiuigi^.(20)Tu=\sum_{i=1}^{m}\frac{L_i}{p_i}u_i\widehat{g_i}. \tag*{(20)}

We now compute the ℓ1\ell_1 and ℓ2\ell_2 norms of TuTu. We have, by the triangle inequality,

∥Tu∥1≤∑i=1mLipi∣ui∣Li=∑i=1mνi∣ui∣.\lVert Tu\rVert_1 \le\sum_{i=1}^{m} \frac{L_i}{p_i}|u_i|L_i = \sum_{i=1}^{m}\nu_i|u_i|.

The Orthogonality and Parseval give equality for ℓ2\ell_2 norm. That is,

∥Tu∥22=∑i=1mLi2pi2∣ui∣2∥gi∥22=∑i=1mνi∣ui∣2.(21)\lVert Tu\rVert_2^2 = \sum_{i=1}^{m}\frac{L_i^2}{p_i^2}|u_i|^2\lVert g_i\rVert_2^2 = \sum_{i=1}^{m}\nu_i|u_i|^2. \tag*{(21)}

Then applying the Reisz-Thorin interpolation theorem (Theorem 2.5), for 1≤r≤21 \le r \le2, we obtain,

∥Tu∥rr≤∑i=1mνi∣ui∣r.\lVert Tu\rVert_r^r \le\sum_{i=1}^{m}\nu_i|u_i|^r.

Now choose ui=pi/Liu_i=p_i/L_i to obtain Tu=f^Tu=\widehat{f}, and thereby we get

∥Tu∥rr=∑S∣f^(S)∣r≤∑i=1mνi∣ui∣r=∑i=1mνi(piLi)r=∑i=1mLi2−rpir−1.\lVert Tu\rVert_r^r = \sum_S|\widehat{f}(S)|^r \le\sum_{i=1}^{m}\nu_i|u_i|^r = \sum_{i=1}^{m}\nu_i\left(\frac{p_i}{L_i}\right)^r = \sum_{i=1}^{m}L_i^{2-r}p_i^{r-1}.

Moreover, it is easily seen from (21) that equality holds at r=2r=2.

We now transfer the moment inequality in Theorem 4.1 to bounds on entropy.

Theorem 4.2. Let f:{−1,1}n→Cf:\{-1,1\}^n \to\mathbb{C} and f=∑i=1mgif=\sum_{i=1}^{m}g_i where the non-zero functions gi:{−1,1}n→Cg_i:\{-1,1\}^n \to\mathbb{C} are pairwise orthogonal. Define pi:=∥gi∥22p_i:=\lVert g_i\rVert_2^2 and Li:=∥gi^∥1L_i:=\lVert\widehat{g_i}\rVert_1. Then,

E(f^2)=∑S⊆[n]∣f^(S)∣2log⁡1∣f^(S)∣2≤2∑i=1mpilog⁡Lipi.(22)\mathcal{E}(\widehat{f}^2)=\sum_{S\subseteq[n]}|\widehat{f}(S)|^2\log\frac{1}{|\widehat{f}(S)|^2}\le2\sum_{i=1}^{m}p_i\log\frac{L_i}{p_i}. \tag*{(22)}

Proof. Define the functions

F(r):=∑S⊆[n]∣f^(S)∣r,andG(r):=∑i=1mLi2−rpir−1.F(r):=\sum_{S\subseteq[n]}|\widehat{f}(S)|^r,\qquad\text{and}\qquad G(r):=\sum_{i=1}^{m}L_i^{2-r}p_i^{r-1}.

We have from Theorem 4.1 that F(r)≤G(r)F(r)\le G(r) for 1≤r≤21\le r\le2 and F(2)=G(2)F(2)=G(2). Thus for t>0t>0,

F(2)−F(2−t)t≥G(2)−G(2−t)t.(23)\frac{F(2)-F(2-t)}{t}\ge\frac{G(2)-G(2-t)}{t}. \tag*{(23)}

Hence, taking the left-derivative at 2, gives F′(2)≥G′(2)F'(2) \ge G'(2). Computing we have

F′(2)=∑S⊆[n]∣f^(S)∣2ln⁡∣f^(S)∣,andG′(2)=∑i=1mpiln⁡piLi.F'(2)=\sum_{S\subseteq[n]}|\widehat{f}(S)|^2\ln|\widehat{f}(S)|,\quad\text{and}\quad G'(2)=\sum_{i=1}^{m}p_i\ln\frac{p_i}{L_i}.

Multiplying each derivative by −2/ln⁡2-2/\ln2 and using the inequality F′(2)≥G′(2)F'(2)\ge G'(2), we obtain

∑S⊆[n]∣f^(S)∣2log⁡1∣f^(S)∣2≤2∑i=1mpilog⁡Lipi.(24)\sum_{S\subseteq[n]}|\widehat{f}(S)|^2\log\frac{1}{|\widehat{f}(S)|^2}\le2\sum_{i=1}^{m}p_i\log\frac{L_i}{p_i}. \tag*{(24)}

Theorem 4.3. Let f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} be a Boolean function. Then, H(f^2)=O(min⁡{aUC0⊕(f),aUC1⊕(f)})\mathrm{H}(\widehat{f}^{2})=O(\min\{\mathrm{aUC}^{\oplus}_{0}(f),\mathrm{aUC}^{\oplus}_{1}(f)\}), where for b∈{0,1}b\in\{0,1\}, aUCb⊕(f)\mathrm{aUC}^{\oplus}_{b}(f) is the average unambiguous bb-parity-certificate complexity of ff.

Proof. Fix b=1b=1 (the other case is analogous). Let g=(1−f)/2g=(1-f)/2 and U1={C1,…,Cm}\mathcal{U}_{1}=\{C_{1},\ldots,C_{m}\} be an unambiguous 1-parity-certificate for ff. Let gi:{−1,1}n→{0,1}g_i:\{-1,1\}^{n}\to\{0,1\} be the indicator function of the 1-parity-certificate CiC_i. Then, it follows by unambiguity that g=∑i=1mgig=\sum_{i=1}^{m}g_i and gig_i's are pairwise orthogonal. From, Lemma 2.4 and Theorem 4.2, we have

H(f^2)≤4 E(g^2)≤8∑i=1m∥gi∥22log⁡∥gi^∥1∥gi∥22=8∑i=1mco-dim⁡(Ci)2−co-dim⁡(Ci)=O(aUC⊕(f,U1)).(25)\mathrm{H}(\widehat{f}^{2})\le4\,\mathcal{E}(\widehat{g}^{2})\le8\sum_{i=1}^{m}\|g_i\|_{2}^{2}\log\frac{\|\widehat{g_i}\|_{1}}{\|g_i\|_{2}^{2}}=8\sum_{i=1}^{m}\operatorname{co-dim}(C_i)2^{-\operatorname{co-dim}(C_i)}=O(\mathrm{aUC}^{\oplus}(f,\mathcal{U}_{1})). \tag*{(25)}

Since U1\mathcal{U}_{1} is arbitrary, we obtain H(f^2)=O(aUC1⊕(f))\mathrm{H}(\widehat{f}^{2})=O(\mathrm{aUC}^{\oplus}_{1}(f)).

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 f:{−1,1}n→Cf:\{-1,1\}^{n}\to\mathbb{C} and f=∑i=1mgif=\sum_{i=1}^{m}g_i where gi:{−1,1}n→Cg_i:\{-1,1\}^{n}\to\mathbb{C}'s are non-zero functions. Define m×mm\times m Gram matrix Γ\Gamma where Γij:=⟨gi,gj⟩=E[gigj‾]\Gamma_{ij}:=\langle g_i,g_j\rangle=\mathbb{E}[g_i\overline{g_j}], and denote Li:=∥gi^∥1L_i:=\|\widehat{g_i}\|_1. Suppose there are numbers ai>0a_i>0 such that

Γ⪯D:=diag⁡(a1,…,am).(26)\Gamma\preceq D:=\operatorname{diag}(a_1,\ldots,a_m). \tag*{(26)}

Then, for every $1\le r\le 2,

∑S⊆[n]∣f^(S)∣r≤∑i=1mLirair−1.(27)\sum_{S\subseteq[n]}|\widehat{f}(S)|^r\le\sum_{i=1}^{m}L_i^r a_i^{r-1}. \tag*{(27)}

If, additionally, the equality holds at r=2r = 2, ∑iai=∥f∥22\sum_i a_i = \|f\|_2^2, then

E(f^2)≤2∑i=1mailog⁡Liai.(28)\mathcal{E}(\widehat{f}^2) \le2\sum_{i=1}^{m} a_i \log\frac{L_i}{a_i}. \tag*{(28)}

Proof. Define νi=Li2/ai\nu_i = L_i^2/a_i for i∈[m]i \in[m], and the linear operator T:Cm→C2nT:\mathbb{C}^m \to\mathbb{C}^{2^n} by

Tu=∑i=1mLiaiuigi^,for all u∈Cm.(29)Tu = \sum_{i=1}^{m} \frac{L_i}{a_i}u_i\widehat{g_i}, \quad\text{for all } u \in\mathbb{C}^m. \tag*{(29)}

As before we compute the ℓ1\ell_1 and ℓ2\ell_2 norms of TuTu. We have, by the triangle inequality,

∥Tu∥1≤∑i=1mLiai∣ui∣∥gi^∥1=∑i=1mLi2ai∣ui∣=∑i=1mνi∣ui∣.\|Tu\|_1 \le\sum_{i=1}^{m}\frac{L_i}{a_i}|u_i|\|\widehat{g_i}\|_1 = \sum_{i=1}^{m}\frac{L_i^2}{a_i}|u_i| = \sum_{i=1}^{m}\nu_i|u_i|.

For ℓ2\ell_2 norm, we first use Parseval and then (26). That is,

∥Tu∥22=∥∑i=1mLiaiuigi^∥22=∥∑i=1mLiaiuigi∥22≤∑i=1mai∣Liaiui∣2≤∑i=1mνi∣ui∣2,\|Tu\|_2^2 = \left\|\sum_{i=1}^{m}\frac{L_i}{a_i}u_i\widehat{g_i}\right\|_2^2 = \left\|\sum_{i=1}^{m}\frac{L_i}{a_i}u_i g_i\right\|_2^2 \le\sum_{i=1}^{m}a_i\left|\frac{L_i}{a_i}u_i\right|^2 \le\sum_{i=1}^{m}\nu_i|u_i|^2,

where the first inequality follows from (26) which implies that for all c∈Cmc \in\mathbb{C}^m, ∥∑i=1mcigi∥22≤∑i=1mai∣ci∣2\left\|\sum_{i=1}^{m}c_i g_i\right\|_2^2 \le\sum_{i=1}^{m}a_i|c_i|^2. Then applying the Reisz-Thorin interpolation theorem (Theorem 2.5), for 1≤r≤21 \le r \le2, we obtain,

∥Tu∥rr≤∑i=1mνi∣ui∣r.\|Tu\|_r^r \le\sum_{i=1}^{m}\nu_i|u_i|^r.

Now choose ui=ai/Liu_i = a_i/L_i to obtain Tu=f^Tu = \widehat{f}, and thereby we get

∥Tu∥rr=∑S∣f^(S)∣r≤∑i=1mνi∣ui∣r=∑i=1mνi(aiLi)r=∑i=1mLi2−rair−1.\|Tu\|_r^r = \sum_S|\widehat{f}(S)|^r \le\sum_{i=1}^{m}\nu_i|u_i|^r = \sum_{i=1}^{m}\nu_i\left(\frac{a_i}{L_i}\right)^r = \sum_{i=1}^{m}L_i^{2-r}a_i^{r-1}.

Furthermore, if ∑iai=∥f∥22\sum_i a_i = \|f\|_2^2, then the arguments from the proof of Theorem 4.2 can be applied here too to obtain a similar bound on entropy

E(f^2)≤2∑i=1mailog⁡Liai.\mathcal{E}(\widehat{f}^2) \le2\sum_{i=1}^{m}a_i\log\frac{L_i}{a_i}.

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 f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} be a Boolean function. Then,

H(f^2)=O(min⁡{avgdeg⁡cj⊕(f),avgdeg⁡cj⊕(−f)}).\mathbb{H}(\widehat{f}^{2})=O\left(\min\left\{\operatorname{avgdeg}_{\mathrm{cj}}^{\oplus}(f),\operatorname{avgdeg}_{\mathrm{cj}}^{\oplus}(-f)\right\}\right).

Proof. Let ff be represented by a conical junta h=∑i=1mwiCih=\sum_{i=1}^{m}w_i C_i where CiC_i's are conjunctions of literals (or, more generally, indicators of affine subspaces). Recall, avgdeg⁡cj(h)=∑i=1mwico-dim⁡(Ci)2−co-dim⁡(Ci)\operatorname{avgdeg}_{\mathrm{cj}}(h)=\sum_{i=1}^{m}w_i\operatorname{co-dim}(C_i)2^{-\operatorname{co-dim}(C_i)}. Since Fourier-entropy is invariant under negation, it suffices to show H(f^2)=O(avgdeg⁡cj(h))\mathbb{H}(\widehat{f}^{2})=O(\operatorname{avgdeg}_{\mathrm{cj}}(h)).

Let g=(1−f)/2=h=∑i=1mgig=(1-f)/2=h=\sum_{i=1}^{m}g_i, where gi=wiCig_i=w_iC_i. Furthermore, let Γ\Gamma be a m×mm\times m Gram matrix with Γij=⟨gi,gj⟩\Gamma_{ij}=\langle g_i,g_j\rangle. Then, Γi,j≥0\Gamma_{i,j}\geq0 and define the row sums ai:=∑jΓij=⟨gi,g⟩a_i:=\sum_j\Gamma_{ij}=\langle g_i,g\rangle and the diagonal matrix D:=diag⁡(a1,…,am)D:=\operatorname{diag}(a_1,\ldots,a_m). It is then easily seen that Γ⪯D\Gamma\preceq D. Indeed, for every c∈Cmc\in\mathbb{C}^{m},

∥∑icigi∥22−∑iai∣ci∣2=−12∑i,jΓij∣ci−cj∣2≤0.\left\|\sum_i c_i g_i\right\|_2^2-\sum_i a_i|c_i|^2=-\frac{1}{2}\sum_{i,j}\Gamma_{ij}|c_i-c_j|^2\leq0.

Also ∑iai=∑i⟨gi,g⟩=∥g∥22\sum_i a_i=\sum_i\langle g_i,g\rangle=\|g\|_2^2, Li:=∥gi^∥1=wiL_i:=\|\widehat{g_i}\|_1=w_i, and ai=wi2−co-dim⁡(Ci)a_i=w_i2^{-\operatorname{co-dim}(C_i)}. Thus, by an application of Lemma 2.4 and Theorem 4.4, we obtain

H(f^2)=O(E(g^2))=O(∑iwi2−co-dim⁡(Ci)co-dim⁡(Ci))=O(avgdeg⁡cj(h)).\mathbb{H}(\widehat{f}^{2})=O(\mathcal{E}(\widehat{g}^{2}))=O\left(\sum_i w_i2^{-\operatorname{co-dim}(C_i)}\operatorname{co-dim}(C_i)\right)=O(\operatorname{avgdeg}_{\mathrm{cj}}(h)).

Application to Quantum Communication Complexity Lower Bound

Let X,YX,Y be finite non-empty sets and let M∈{−1,1}X×YM\in\{-1,1\}^{X\times Y} be a total sign matrix. The quantity Qε∗,cc(M)Q^{*,\mathrm{cc}}_{\varepsilon}(M) is the minimum worst-case number of qubits communicated by a two-party protocol that outputs MxyM_{xy} with error at most ε\varepsilon on every input (x,y)(x,y). Arbitrary finite-dimensional prior entanglement and local ancillas are allowed. Bob is the designated output party. For probability vectors u=(ux)x∈Xu=(u_x)_{x\in X} and v=(vy)y∈Yv=(v_y)_{y\in Y}, let

Au,v=DuMDv,where Du=diag⁡(ux)x∈X and Dv=diag⁡(vy)y∈Y.(30)A_{u,v}=D_{\sqrt{u}}MD_{\sqrt{v}},\qquad\text{where }D_{\sqrt{u}}=\operatorname{diag}(\sqrt{u_x})_{x\in X}\text{ and }D_{\sqrt{v}}=\operatorname{diag}(\sqrt{v_y})_{y\in Y}. \tag*{(30)}

Let σ1(Au,v)≥σ2(Au,v)≥⋯≥0\sigma_1(A_{u,v})\geq\sigma_2(A_{u,v})\geq\cdots\geq0 be the singular values of Au,vA_{u,v}. Since

∑iσi(Au,v)2=∥Au,v∥F2=∑x,yuxvy∣Mxy∣2=1,(31)\sum_i\sigma_i(A_{u,v})^2=\|A_{u,v}\|_F^2=\sum_{x,y}u_xv_y|M_{xy}|^2=1, \tag*{(31)}

their squares form a probability distribution. Define

Hu,v(M)=∑iσi(Au,v)2log⁡1σi(Au,v)2,(32)H_{u,v}(M)=\sum_i\sigma_i(A_{u,v})^2\log\frac{1}{\sigma_i(A_{u,v})^2}, \tag*{(32)}

with 0log⁡(1/0)=00\log(1/0)=0. We now show that supremum over all probability distributions uu and vv lower bounds the quantum communication complexity.

Theorem 5.1. For every 0≤ε<1/20 \le\varepsilon< 1/2, there is a constant cε>0c_\varepsilon> 0 such that, for every total sign matrix MM and every pair of probability vectors u,vu,v,

Qε∗,cc(M)≥cεHu,v(M).Q_{\varepsilon}^{*,\mathrm{cc}}(M) \ge c_\varepsilon H_{u,v}(M).

In particular, for f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\}, let Mf(x,y)=f(x⊕y)M_f(x,y)=f(x\oplus y), uu and vv be uniform distributions, and then we have

Qε∗,cc(Mf)≥cεH(f^ 2).Q_{\varepsilon}^{*,\mathrm{cc}}(M_f) \ge c_\varepsilon H(\widehat{f}^{\,2}).

For uniform N×NN \times N sign matrices, let E=Hu,v(M)E=H_{u,v}(M). Linial–Shraibman prove the bounded-error estimate

Q1/3∗,cc(M)≥Ω(E1+log⁡((log⁡N)/E)),E>0.Q_{1/3}^{*,\mathrm{cc}}(M) \ge\Omega\left(\frac{E}{1+\log((\log N)/E)}\right), \qquad E>0.

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 BB, let ∥B∥tr=∑iσi(B)\lVert B\rVert_{\mathrm{tr}}=\sum_i \sigma_i(B) denote its trace norm, and let ∥B∥max⁡=max⁡x,y∣Bxy∣\lVert B\rVert_{\max}=\max_{x,y}|B_{xy}|. Define the factorization norm

γ2(B)=inf⁡B=UV∗(max⁡x∥Ux∥2)(max⁡y∥Vy∥2),(33)\gamma_2(B)=\inf_{B=UV^*}\left(\max_x\lVert U_x\rVert_2\right)\left(\max_y\lVert V_y\rVert_2\right), \tag*{(33)}

where Ux,VyU_x,V_y are rows. We need the following facts about various norms.

Lemma 5.2 ([2 Corollary IV.2.6]). For every matrix BB and every pair of probability vectors u,vu,v,

∥DuBDv∥tr≤γ2(B).\left\lVert D_{\sqrt{u}}BD_{\sqrt{v}}\right\rVert_{\mathrm{tr}} \le\gamma_2(B).

Lemma 5.3 ([2 Theorem IV.3.4]). If A,BA,B have the same dimensions and ai,bia_i,b_i are their singular values in decreasing order, then

∑i(ai−bi)2≤∥A−B∥F2.\sum_i(a_i-b_i)^2\le\lVert A-B\rVert_F^2.

We also need the following lemma from [20] about γ2\gamma_2-norm of the matrix of acceptance probabilities.

Lemma 5.4 ([20 Lemma 10]). If PxyP_{xy} is the acceptance probability of a protocol with communication

cost qq, then γ2(P)≤2q\gamma_2(P) \le2^q. For its expected signed output matrix B=2P−JB = 2P - J, where JJ is all ones,

γ2(B)≤2γ2(P)+1≤2q+1+1≤2q+2.\gamma_2(B) \le2\gamma_2(P) + 1 \le2^{q+1} + 1 \le2^{q+2}.

We are now ready to prove Theorem 5.1.

Proof of Theorem 5.1. Let MM be any sign matrix, and assume, without loss of generality, q:=Qε∗,cc(M)≥1q := Q_{\varepsilon}^{*,\mathrm{cc}}(M) \ge1. For every integer j≥1j \ge1, amplify a cost qq protocol by independent repetition and majority until its error is at most ηj=2−j/2−1\eta_j = 2^{-j/2-1}. Let the cost of this amplified protocol be qj=Oε(q(j+1))q_j = O_{\varepsilon}(q(j + 1)). Let Pj(x,y)P_j(x,y) be the probability that this amplified protocol outputs +1+1, and define its expected signed output Bj=2Pj−JB_j = 2P_j - J, where JJ is the all-ones matrix. From the correctness of the protocol, we then have

∥M−Bj∥max⁡≤2ηj=2−j/2,andγ2(Bj)≤2qj+2.(34)\lVert M - B_j\rVert_{\max} \le2\eta_j = 2^{-j/2}, \qquad\text{and} \qquad\gamma_2(B_j) \le2^{q_j+2}. \tag*{(34)}

where the second estimate is Lemma 5.4. Let A=Au,vA = A_{u,v} and Aj=DuBjDvA_j = D_{\sqrt{u}}B_jD_{\sqrt{v}}. Then pointwise approximation (34) imply

∥A−Aj∥F2=∑x,yuxvy∣Mxy−(Bj)xy∣2≤2−j.(35)\lVert A - A_j\rVert_{\mathrm{F}}^2 = \sum_{x,y} u_xv_y\lvert M_{xy} - (B_j)_{xy}\rvert^2 \le2^{-j}. \tag*{(35)}

Lemma 5.2 gives ∥Aj∥tr≤γ2(Bj)≤2qj+2\lVert A_j\rVert_{\mathrm{tr}} \le\gamma_2(B_j) \le2^{q_j+2}, and therefore log⁡max⁡{1,∥Aj∥tr}=Oε(q(j+1))\log\max\{1,\lVert A_j\rVert_{\mathrm{tr}}\} = O_{\varepsilon}(q(j+1)). Let

s=(σi(A))i,s(j)=(σi(Aj))i,s = (\sigma_i(A))_i, \qquad s^{(j)} = (\sigma_i(A_j))_i,

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),

∥s−s(j)∥22≤2−j.\lVert s - s^{(j)}\rVert_2^2 \le2^{-j}.

Moreover, ∥s∥2=1\lVert s\rVert_2 = 1 and ∥s(j)∥1=∥Aj∥tr\lVert s^{(j)}\rVert_1 = \lVert A_j\rVert_{\mathrm{tr}}, so log⁡max⁡{1,∥s(j)∥1}=Oε(q(j+1))\log\max\{1,\lVert s^{(j)}\rVert_1\} = O_{\varepsilon}(q(j+1)). Now using Theorem 3.1 with ss and s(j)s^{(j)} gives

Hu,v(M)=Oε(q)=Oε(Qε∗,cc(M)).H_{u,v}(M) = O_{\varepsilon}(q) = O_{\varepsilon}(Q_{\varepsilon}^{*,\mathrm{cc}}(M)).

In particular, when MfM_f is a XOR-matrix of a Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n \to\{-1,1\}, then Fourier-entropy of ff lower bounds the quantum communication cost of f(x⊕y)f(x \oplus y),

Qε∗,cc(Mf)=Ωε(H(f^ 2)).Q_{\varepsilon}^{*,\mathrm{cc}}(M_f) = \Omega_{\varepsilon}(\mathrm{H}(\widehat{f}^{\,2})).

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. [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. [2]R. Bhatia. Matrix Analysis. Springer New York, NY, 1997.
  3. [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. [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. [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. [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. [7]T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991.
  8. [8]B. Das, M. Pal, and V. Visavaliya. The entropy influence conjecture revisited, 2011. arxiv:1110.4301.arxiv.org/abs/1110.4301
  9. [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. [10]G. B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley and Sons, Inc., 2nd edition, 1999.
  11. [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. [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. [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. [14][Han25] X. Han. A new bound for the Fourier-entropy-influence conjecture. Combinatorica, 45, 2025. Article 4.arxiv.org/abs/2312.08271
  15. [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. [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
  17. [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
  18. [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.
  19. [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.
  20. [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.
  21. [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
  22. [23][O’D14] R. O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.arxiv.org/abs/2105.10386
  23. [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
  24. [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
  25. [26]G. Shalev. On the Fourier Entropy Influence conjecture for extremal classes. arxiv:1806.03646, 2018.arxiv.org/abs/1806.03646
  26. [27]Y. Shmalo. Fourier entropy of threshold functions and their compositions, October 2026. arXiv:2610.16069, preprint.arxiv.org/abs/2610.16069
  27. [28]R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, 2008. ToC Library, Graduate Surveys 1.
  28. [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

Paper details

vlnc:W_kks9vfnh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents