Plaintext
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13
www.theoryofcomputing.org
Fourier Sparsity and Dimension
Swagato Sanyal
Received December 29, 2018; Revised August 19, 2019; Published October 27, 2019
Abstract: We prove that the Fourier dimension of any Boolean function with Fourier
√
sparsity s is at most O ( s log s). This bound is tight up to a factor of O(log s) since the
Fourier dimension and sparsity of the address function are quadratically related. We obtain
our result by bounding the non-adaptive parity decision tree complexity, which is known to
be equivalent to the Fourier dimension. A consequence of our result is that any XOR function
√
has a protocol of complexity O( r log r) in the simultaneous communication model, where
r is the rank of its communication matrix.
ACM Classification: F.2.3
AMS Classification: 68Q17
Key words and phrases: Boolean functions, Fourier analysis, Boolean complexity, decision tree, query
complexity
1 Introduction
The study of Boolean functions involves studying various complexity measures and their inter-relation-
ships. Two such measures, which we investigate in this article, are the Fourier dimension and the Fourier
sparsity. Let f : Fn2 → {1, −1} be a Boolean function with Fourier expansion
f (x) = ∑ fb(γ)χγ (x).
γ∈Fn2
n
where χγ (x) := (−1)∑i=1 γi xi are the characters and the fb(γ)’s are real numbers, called the Fourier coeffi-
cients of f . The Fourier dimension and Fourier sparsity are defined as follows.
A conference version of this paper appeared in the Proceedings of the 42nd International Colloquium on Automata,
Languages, and Programming (ICALP 2015) [12].
© 2019 Swagato Sanyal
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a011
S WAGATO S ANYAL
Definition 1.1 (Fourier sparsity and dimension). For a Boolean function f : Fn2 → {1, −1} with Fourier
expansion
f (x) = ∑ fb(γ)χγ (x),
γ∈Fn2
the Fourier support of f , denoted by supp( fb), is defined as
supp( fb) := {γ ∈ Fn2 : fb(γ) 6= 0}.
The Fourier sparsity of f , denoted by sparsity( fb), is defined as the size of the Fourier support of f , i. e.,
sparsity( fb) := | supp( fb)|,
while the Fourier dimension dim( fb) of f is defined as the dimension of the span of supp( fb).
Note that the Fourier expansion of f is a multilinear polynomial in the variables yi := (−1)xi . With
respect to this view, Fourier sparsity of a Boolean function f is the number of monomials that appear in
the Fourier expansion of f . Fourier dimension, on the other hand, is the smallest number of monomials,
or equivalently parity functions, whose values always determine f . It is natural to investigate the power
and limitation of polynomials with low Fourier sparsity or Fourier dimension. Fourier sparsity and
Fourier dimension were studied by Gopalan et al. [4] in the context of property testing. More recently
these quantities have been studied in the context of learning [7, 1]. An approximate analog of Fourier
dimension has been shown to characterize the randomized one-way communication complexity of an
important and well-studied subclass of functions called the XOR functions, over uniformly distributed
inputs [8]. A Boolean function F(x, y) on two n-bit inputs is an XOR function if there exists a Boolean
function f on n bits such that F(x, y) = f (x ⊕ y).
Besides, the study on Fourier sparsity has attracted attention of complexity theorists due to its intimate
connection to the log-rank conjecture of communication complexity. Fourier dimension is related to a
simultaneous communication game. This connection is discussed in more detail later in this section.
The following inequalities easily follow from the definition of Fourier sparsity and dimension.
log2 sparsity( fb) ≤ dim( fb) ≤ sparsity( fb). (1.1)
There are functions (e.g., indicator functions of subspaces) for which the first inequality is tight (i. e.,
holds with equality). In this note we examine the tightness of the second inequality. Note that the
Fourier transform of a Boolean function is a polynomial with a very special property; it evaluates to
1 or −1 on all inputs from {1, −1}n . It is thus natural to expect that there is always a good amount of
dependency amongst its monomials. The gap between Fourier sparsity and Fourier dimension is one way
of quantifying this dependency.
For the second inequality, the address function is one function having asymptotically the closest
gap between Fourier
√ dimension and sparsity.1 Let s be a power of 2. The address function Adds :
{0, 1}(1/2) log s+ s → {1, −1} is defined as
1
Adds (x, y1 , y2 , . . . , y√s ) := (−1)yx , x ∈ {0, 1} 2 log s , yi ∈ {0, 1},
1 Recently Khalyavin, Lobanov and Tarannikov have constructed a function for which the gap between Fourier dimension
and Fourier sparsity is closer by a constant factor than in the address function [9].
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 2
F OURIER S PARSITY AND D IMENSION
√
where x is interpreted as an address in {1, . . . , s}. In other words, on every input (x, y), Adds (x, y) is
the value of the addressed input bit yx indexed by the addressing variables x. The address function has
√
Fourier sparsity s and Fourier dimension at least s. To see this, note that
Adds (x, y) = ∑ 1x=x̃ · (−1)yx̃ .
x̃∈{0,1}(1/2) log s
√ √
Each indicator function 1x=x̃ has Fourier sparsity2 s. Since the summation is over s terms, and since
there is no cancellation due to the presence of a character corresponding to a fresh variable yx̃ in each
√ √
term, the Fourier sparsity of the address function is equal to s · s = s. To see that the dimension is at
√
least s, note that for each x̃ ∈ {0, 1}(1/2) log s , the character (−1)yx̃ appears in the Fourier transform. We
prove that for any Boolean function, this is the asymptotically highest possible value of dim( fb) in terms
of sparsity( fb), up to a factor of O(log s). This was presented as an open problem at the Simons workshop
on Real Analysis in Testing, Learning and Inapproximability, 2013 by John Wright.
Our main result is the following.
√
Theorem 1.2. Let f be a Boolean function with sparsity( fb) = s. Then, dim( fb) = O ( s log s).
In a preliminary version of this article, posted on arXiv and ECCC, we proved an upper bound of
O(s2/3 ) on dim( fb). Avishay Tal observed that the analysis can be tightened to obtain the near-optimal
√
upper bound of O ( s log s).
Prior to this work, Gavinsky et al. [3] had proved that the dimension of any Boolean function with
Fourier sparsity s is O(s/ log s).
Theorem 1.2 is proved using a lemma of Tsang et al. [14] bounding the codimension of an affine
subspace restricted to which the function is constant, in terms of the Fourier sparsity of the function. The
following result is a corollary to [14, Lemma 28].
Lemma 1.3 (Tsang, Wong, Xie, and Zhang). Let f : Fn2 → {1, −1} be a Boolean function with Fourier
√
sparsity s. Then there is an affine subspace V of Fn2 of codimension O( s) such that f is constant on V .
Proof idea of Theorem 1.2. We begin with a simple but crucial observation made by Gopalan et al. [4],
that the Fourier dimension of a Boolean function is equivalent to its non-adaptive parity decision tree
complexity (see Proposition 2.7). This offers us a potential approach towards an upper bound on the
Fourier dimension of a Boolean function: exhibiting a shallow non-adaptive parity decision tree of the
function. We recall that the character functions essentially compute the parities of various subsets of the
input bits. Thus a parity decision tree can be thought of as querying various character functions. Parity
functions, in turn, are linear functions from Fn2 to F2 ; thus affine subspaces can be described by specifying
a set of parities that are set to various values.
Towards this end, we first recall the construction of an (adaptive) parity decision tree for a Boolean
function f of Fourier sparsity s by Tsang et al. [14], which in turn improves on an earlier construction
due to Shpilka et al. [13, Theorem 1.1]. The broad idea of their construction is as follows. At any point
in time, a partial tree is maintained whose leaves are functions which are restrictions of f on different
2 Note that the indicator functions evaluate to {0, 1} instead of {1, −1}. However, the theory of Fourier analysis extends to
such functions as well.
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 3
S WAGATO S ANYAL
affine subspaces. Then a non-constant leaf τ is picked arbitrarily, and a small set of linear restrictions is
obtained by invoking Lemma 1.3, such that the restricted function f |τ at that leaf becomes constant. The
next step is observing that if f |τ is further restricted to all the affine subspaces obtained by setting the
same set of parities in all possible ways, then the Fourier sparsity of each of the corresponding restricted
functions is at most half of that of f |τ . This is because, in the former restriction, since the function
becomes constant, the Fourier coefficients corresponding to non-constant characters must disappear in
the restricted space. This can only happen if every non-constant character gets identified with at least one
other character. This identification leads to halving of the Fourier support. Note that by Lemma 1.3 the
number of queries we have spent to achieve this reduction in Fourier sparsity is
q
O sparsity( f |τ ) .
d
√
A calculation gives us that proceeding in this way a parity decision tree of depth O( s) is obtained.
Note that the choice of parities restricted at various steps depends on the leaf (function) chosen, and
hence on the outcomes of the preceding queries. Thus the constructed tree is an adaptive one. In this
article, we make this tree non-adaptive, at the cost of a logarithmic increase in depth. At each step, we
choose an appropriate function (leaf) of the partial tree constructed thus far, invoke Lemma 1.3, and
obtain restrictions which make it constant. Then we query the same set of parities at every leaf. Note
that doing that in each step results in a non-adaptive tree, as the set of parities queried at each step is the
same for all the leaves of the current partial tree, and hence independent of the responses to the previous
queries. Then we argue that this leads to a significant reduction of Fourier sparsity. Let s(i) be the Fourier
sparsity of the function (leaf) chosen at the i-th step. It can be shown that, in the next step, the size `(i) of
the union of the Fourier supports of√all the leaves falls at least by s(i) /2. From Lemma 1.3, the number of
queries spent in the i-th step is O( s(i) ). Using the Uncertainty Principle (Theorem 2.4) we show that
2
s(i) ≥ `(i) /s (see Lemma 3.3). We combine all these facts to show that continuing in this fashion, in a
√
small number of steps and making at most O( s log s) queries, all the leaves become constant functions.
The details of the construction of the non-adaptive parity decision tree, and its analysis, are given in
Section 3.
Connections to communication complexity and the log-rank conjecture. The log-rank conjecture
is a long-standing and important conjecture in communication complexity. The statement of the conjecture
is that the deterministic communication complexity of a Boolean function is asymptotically bounded
above by some fixed polylogarithm of the rank (over the real numbers) of its communication matrix. The
best known
√ upper bound of deterministic communication complexity of a function in terms of the rank
is O( rank log rank) due to Lovett [10].3 The rank of the communication matrix of an XOR function
F(x, y) := f (x ⊕ y) is known to be equal to the Fourier sparsity s of f . For the special case of XOR
functions the result by Lovett also follows from a result of of Tsang et al. [14],4 which improves on a
result by Shpilka et al. [13]. A consequence of Theorem 1.2 is that XOR functions admit a protocol
3 We note here that the related log approximate-rank conjecture has recently been refuted by Chattopadhyay et al. [2], and
the function they use is an XOR function. √ √
4 For XOR functions, the communication complexity upper bound is in fact O( rank) which is better than O( rank log rank)
by a logarithmic factor. It follows from the parity decision tree complexity upper bound proved by Tsang et al. [14].
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 4
F OURIER S PARSITY AND D IMENSION
√ √
of complexity O( rank log rank) = O( s log s) in the simultaneous communication model.5 We note
that both the earlier protocols [10, 14] are two-way. The simultaneous protocol is as follows. Alice and
√
Bob a priori agree on a set S of O( s log s) parities that span the Fourier support of F(x, y) = f (x ⊕ y).
The existence of S is guaranteed by Theorem 1.2. The character corresponding to each parity P in S
is a product of a character Mx in variables in x and a character My in variables in y. Upon receiving
inputs x and y, Alice and Bob compute the values of Mx and My , respectively, for each P ∈ S, and send
the evaluations to the referee. The referee then can evaluate the characters corresponding to each parity
P ∈ S on the input x ⊕ y. Since every other character in the Fourier expansion of F is determined by the
characters in S, the referee can compute the value of all those characters. Finally, the referee evaluates
F(x, y) from its Fourier expansion and outputs it.
Some remarks about Lemma 1.3. Lemma 1.3 is not believed to be tight. Tsang et al. [14] investigated
this question while studying the log-rank conjecture for XOR functions. They suggested a direction
towards proving the log-rank conjecture for XOR functions. In particular, they proposed a protocol for an
XOR function F(x, y) = f (x ⊕ y) based on a parity decision tree of f and showed that the communication
complexity of the proposed protocol is polylogarithmic in the rank of the communication matrix if the
following related conjecture, stated as [14, Conjecture 27], is true.
Conjecture 1.4 (Tsang et al.). There exists a constant c > 0 such that for every Boolean function f with
Fourier sparsity s, there exists an affine subspace of codimension O (logc s) on which f is constant.
Even before, Montanaro and Osborne [11] had conjectured that the parity decision tree complexity
of a function is polylogarithmic in its Fourier sparsity. Tsang et al. showed that this seemingly stronger
conjecture follows from Conjecture 1.4.
Tsang et al. proved the above conjecture for certain classes of functions, which include functions
with constant F2 degree, and proved Lemma 1.3 for general functions. It follows from subsequent result
by Hatami, Hosseini and Lovett [6] that Conjecture 1.4 is equivalent to the log-rank conjecture for XOR
functions (and also to the conjecture by Montanaro and Osborne).
We remark that the bound of Theorem 1.2 is near-optimal; so any significant improvement to it
assuming Conjecture 1.4 would be a contradiction, and hence would serve to refute Conjecture 1.4. We
note that with our proof technique and analysis, any improvement to Lemma 1.3 (in particular a positive
resolution of Conjecture 1.4), does not yield a better than logarithmic improvement to Theorem 1.2. Our
result, thus, does not seem to throw any light on the truth of Conjecture 1.4. For further discussion on this
topic, the reader is referred to Section 3.
2 Preliminaries
Let f : Fn2 → {1, −1} be a Boolean function. For γ = (γ1 , . . . , γn ), x = (x1 , . . . , xn ) ∈ Fn2 , let χγ (x) :=
n
(−1)∑i=1 γi xi be the character associated with γ. It is well known that every Boolean function f (x) can be
5 We thank the anonymous referee for pointing this out.
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 5
S WAGATO S ANYAL
uniquely written as
f (x) = ∑ fb(γ)χγ (x). (2.1)
γ∈Fn2
The right-hand side of Equation (2.1) is called the Fourier expansion of f , and the real coefficients fb(γ)
are called the Fourier coefficients.
We review some standard definitions and facts about the Fourier coefficients.
Definition 2.1. Let f (x) = ∑γ∈Fn fb(γ)χγ (x) be a Boolean function, and p ≥ 1. The p-th spectral norm
2
kfb
b k p of f is defined as
!1/p
p
kfb
b kp = ∑ fb(γ) .
γ∈Fn2
kfb
Lemma 2.2 (A special case of Parseval’s identity). For a Boolean function f , b k2 = 1.
The 1st spectral norm of a Boolean function can be bounded in terms of sparsity as follows.
√
kfb
Claim 2.3. For a Boolean function f with Fourier sparsity s, b k1 ≤ s.
Proof.
√ √
kfb
b k1 ≤ b
kfb
k2 · s = s.
The first inequality is the Cauchy-Schwarz inequality while the second equality follows from Lemma 2.2.
In order to prove our results, we shall use the following version of the Uncertainty Principle. See,
e.g., [5] for a proof.
Theorem 2.4 (Uncertainty Principle). Let p : Rn → R be a real multilinear non-zero n-variate polynomial
with sparsity s (i. e., it has s monomials with non-zero coefficients). Let Un denote the uniform distribution
on {1, −1}n . Then
1
Pr [p(x) 6= 0] ≥ .
x∼Un s
As mentioned in the Introduction, we need the following result by Tsang et al. [14, Lemma 28].
Theorem 2.5 (Tsang et al.). Let f : Fn → {1, −1} be such that b
2 kfbk1 = A. Then there is an affine subspace
V of Fn2 of codimension O(A) such that f is constant on V .
Lemma 1.3 is a simple corollary of this theorem via Claim 2.3.
In our proof we crucially use the observation made by Gopalan et al. [4] about the equivalence of the
non-adaptive parity decision tree complexity of a function (defined below) and its Fourier dimension. We
state it in Proposition 2.7.
Definition 2.6 (Non-adaptive parity decision tree complexity). Let f be a Boolean function. The non-
adaptive parity decision tree complexity of f (denoted by NADT⊕ ( f )) is defined as the minimum
integer t such that there exist γ1 , . . . , γt ∈ Fn2 such that f is determined by the evaluation of the characters
χγ1 , . . . , χγt .
Proposition 2.7 (Gopalan et al. [4]). For every Boolean function f , NADT⊕ ( f ) = dim( fb).
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 6
F OURIER S PARSITY AND D IMENSION
3 Upper bound on parity decision tree complexity
In this section, we prove an upper bound on the non-adaptive parity decision tree complexity of a Boolean
function f in terms of its Fourier sparsity s. For B ⊆ Fn2 , let f |B denote the restriction of the function f
to the set B. We will often identify vectors γ ∈ Fn2 with the linear function that maps a vector x ∈ Fn2 to
γ(x) := ∑ni=1 γi xi mod 2 ∈ F2 . We first formally present a procedure NA DT that constructs a non-adaptive
parity decision tree of f . We then provide a description of the procedure in words (in particular, the roles
of the various variables used) and a formal analysis of the same, leading up to the proof of Theorem 1.2.
NA DT( f )
Input: Boolean function f : Fn2 → {1, −1};
Output: A set Γ of parities, whose evaluations determine the value of f ;
1. Set Γ ← ∅, S ← supp( fb) and F ← { f }.
2. While S 6= {0},
/ do
(a) Let g be a function in F with the largest Fourier sparsity. Let A be a largest affine
subspace on which g is constant (breaking ties arbitrarily), with codimension ng . Let
γ1 , . . . , γng ∈ Fn2 and b1 , . . . , bng ∈ F2 be such that
A = {x ∈ Fn2 : γ1 (x) = b1 , . . . , γng (x) = bng }.
(b) Set Γ ← Γ ∪ {γ1 , . . . , γng }.
|Γ|
(c) For each b = (bγ )γ∈Γ ∈ F2 , let Vb be the affine subspace {x ∈ Fn2 : ∀γ ∈ Γ, γ(x) = bγ }.
Set
F←
[
{ f |Vb }.
|Γ|
b∈F2
(d) S ←
S
h∈F supp(h).
b
3. Return Γ.
Notation. After each iteration of the while loop in the procedure, Γ is the set of parities that have been
queried so far, F is the set of all restrictions of f to the affine subspaces obtained by different assignments
to parities in Γ, and S is the union of the Fourier supports of functions in F. Throughout this section, i will
stand for the index of an arbitrary iteration of NA DT. Let Γ(i) , F(i) and S(i) denote Γ, F and S respectively
at the end of the i-th iteration of the while loop. Let Γ(0) = ∅, F(0) = { f } and S(0) = supp( fb).
|Γ(i) |
For each i, let b = (bγ )γ∈Γ(i) ∈ F2 and let Vb be the affine subspace defined by the linear constraints
{γ(x) = bγ : γ ∈ Γ(i) }. In Vb , more than one linear function of the original space may get identified,
namely, the restrictions of these linear functions to the sub-domain subdomain Vb are either the same
function or negations of each other. More specifically, δ1 and δ2 get identified in Vb if and only if
δ1 + δ2 ∈ span Γ(i) (i. e., they belong to the same coset of the subspace span Γ(i) ). This equivalence
relation induces a partition on supp( fb) into equivalence classes. Note that this partition is determined by
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 7
S WAGATO S ANYAL
|Γ(i) |
Γ(i) alone. Further, for each equivalence class, for every b ∈ F2 , the linear functions belonging to that
class get identified with one another in Vb .
(i)
Let `(i) denote the number of such equivalence classes.6 For all j ∈ [`(i) ], let β j be an arbitrarily
picked representative element in the j-th equivalence class. Let
(i) (i) (i) (i)
β j + α j,1 , . . . , β j + α (i)
j,k j
(i) (i) (i)
be the k j elements in the j-th equivalence class, where α j,1 , . . . , α (i) are in span Γ(i) . Now define
j,k j
functions
(i)
kj
(i) (i) (i)
Pj (x) := f
∑ j
b β + α j,l χα (i) (x).
j,l
l=1
(i) (i)
Note that the functions Pj are non-zero. As we will soon see, it will be helpful to think of the Pj ’s as
multilinear polynomials in variables yi = (−1)xi .
Given this notation, we can then write the Fourier expansion of f in the following form:
`(i)
(i)
f (x) = ∑ Pj (x)χβ (i) (x).
j
j=1
(i)
Note that the value of each Pj is fixed once the evaluation of each linear form γ ∈ Γ(i) is specified.
(i)
In other words, each Pj is a constant function on each Vb .
`(i)
(i)
Observation 3.1. ∑ k j = s.
j=1
Proof. The size of the Fourier support of f is the sum of the sizes of its equivalence classes defined
above.
Proposition 3.2. |S(i) | = `(i) .
Proof. Clearly |S(i) | ≤ `(i) , as each term in the Fourier expansion of f |Vb corresponds to a distinct
(i)
equivalence class (and this correspondence is independent of b). Now, for j ∈ [`(i) ], since Pj is a
(i)
non-zero function, there exists an assignment b to the parities in Γ(i) on which Pj evaluates to a non-zero
(i)
value. Thus the coefficient of β j is non-zero in the restriction of f to the affine subspace obtained
(i)
by assigning b to the parities in Γ(i) . Thus for all j ∈ [`(i) ], β j ∈ S(i) which, together with |S(i) | ≤ `(i) ,
implies |S(i) | = `(i) .
We now argue that after every iteration of the while loop, there exists a function h ∈ F(i) which has
large Fourier support.
6 `(i) is in fact the number of cosets of the subspace span Γ(i) with which supp( fb) has non-empty intersection.
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 8
F OURIER S PARSITY AND D IMENSION
2
Lemma 3.3. After the i-th iteration, there exists an h ∈ F(i) such that | supp(b
h)| is at least `(i) /s.
Proof. Consider any function f |Vb ∈ F(i) . The Fourier decomposition of f |Vb is given by
`(i)
(i)
f |Vb = ∑ Pj (b) · χβ (i) (x).
j
j=1
(i) (i)
f |Vb )| is exactly the number of functions Pj , j ∈ [`(i) ] such that Pj (b) is non-zero. We
Thus, | supp( d
|Γ(i) |
analyze this quantity as follows. Pick a b ∈ F2 uniformly at random. Now, note that for each j ∈ [`(i) ],
(i)
Pj is a non-zero multilinear polynomial in variables {(−1)bγ : γ ∈ Γ(i) }. Thus by Theorem 2.4,
(i) 1
Pr[Pj (b) 6= 0] ≥ (i)
.
b kj
Thus,
h i `(i) 1
Eb | supp( f |Vb )| ≥ ∑ (i)
d
j=1 k j
1
≥ `(i) · (i) [By Jensen’s inequality applied to 1/x]
(i)
∑`j=1 k j /`(i)
2
`(i)
= [By Observation 3.1].
s
2
Hence, there exists an h ∈ F(i) such that | supp(b
h)| is at least `(i) /s.
Let g(i) be the function chosen in step 2a of the i-th iteration of NA DT. Let sparsity(gc
(i) ) = s(i) , and
(i)
∆` = ` (i−1) (i)
− ` for i ≥ 1. The next lemma proves that, if a function with large Fourier support is
picked in step 2a, then that leads to a large reduction in the size of S.
Lemma 3.4. Assume that neither f nor 1 − f is a character, and NA DT( f ) runs for t iterations. Then
for all i ∈ [t], ∆`(i) ≥ s(i) /2.
n
Proof. Let γ1 , . . . , γn (i) be the parities queried in iteration i. Hence there is a b = (b1 , . . . , bn (i) ) ∈ (F2 ) g(i)
g g
such that g(i) is constant on the affine subspace Vb obtained by setting γ j to b j for all j ∈ [ng(i) ]. Now,
consider the following cases.
Case 1. s(i) ≥ 2. Since g(i) is constant on Vb , each Fourier coefficient of g(i) |Vb must be either 0 or
±1. This is possible only if for every α ∈ supp(gc (i) ) there is another α ∈ supp(gc(i) ) such that
1 2
α1 + α2 ∈ span{γ1 , . . . , γn (i) }, i. e., they get identified. This implies that for every
g
n
b0 = (b0 ) j ∈ (F2 ) g(i) ,
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 9
S WAGATO S ANYAL
in the affine space Vb0 obtained by restricting each γ j to b0j , every parity in supp(gc (i) ) is identified
with some other parity in supp(gc (i) ) ⊆ S(i−1) , it follows that |S(i) | is at least
(i) ). Since supp(gc
| supp(gc(i) )|/2 less than |S(i−1) |. By Proposition 3.2 this implies ∆`(i) ≥ s(i) /2.
Case 2. s(i) = 1 (i. e., g(i) is either a parity function or the complement of a parity function). Since neither
f nor 1 − f is a character, we have that s(1) = sparsity( fb) ≥ 2. Hence we conclude that i ≥ 2. Note
that for i ≥ 1, 0/ ∈ S(i) . Hence for i ≥ 2, ∆`(i) = 1 ≥ s(i) /2.
The lemma follows from the two cases.
Now we are ready to prove Theorem 1.2.
Proof of Theorem 1.2. If either f or 1 − f is a character, the theorem follows immediately. Hence assume
that neither f nor 1 − f is a character.
We obtain a non-adaptive parity decision tree for f by running NA DT. Assume that the while loop
runs for t iterations. Let the number
√ of queries made in step 2a in the i-th iteration of the procedure be
q(i) . By Lemma 1.3, q(i) = O( s(i) ). By Lemma 3.4, ∆`(i) ≥ s(i) /2. Hence,
q(i) 1
(i)
= √ .
∆` Ω( s(i) )
2 √
From Lemma 3.3 we have s(i) ≥ `(i−1) /s. Hence q(i) = s · O ∆`(i) /`(i−1) . Thus the total number
of queries made within the while loop of the procedure is
!
t t (i) √ t
√ ∆`(i)
(i) ∆`
∑ q = s · ∑ O `(i−1) = s · ∑ O i−1
i=1 i=1 i=1
s − ∑ ∆`( j)
j=1
√ t
1 1 1
≤ s· ∑ O i−1
+ i−1
+···+ i−1
i=1 ( j) ( j)
s − ∑ ∆` s − ∑ ∆` −1 s − ∑ ∆`( j) − (∆`(i) − 1)
j=1 j=1 j=1
!
√ s √
1
≤ s·O ∑k = O( s log s).
k=1
√
From Proposition 2.7 it follows that dim( fb) = O( s log s).
Discussion. As mentioned in the introduction, a potential approach towards disproving Conjecture 1.4
√
is to assume it to be true, and prove that it implies a o( s) upper bound on Fourier dimension. This will
refute the conjecture, since, for the address function (see Section 1),
q
dim(Adds ) = Θ
[ \
sparsity(Adds ) .
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 10
F OURIER S PARSITY AND D IMENSION
However, we cannot disprove the conjecture by an analysis of the NA DT, assuming the conjecture. To see
this let us consider the execution of NA DT on the address function. Recall that Adds (x, y1 , y2 , . . . , y√s ) =
yx , x ∈ {0, 1}(1/2) log s , yi ∈ {0, 1}. One easily sees that a largest affine subspace V on which the function
is constant is the one defined by the constraints x = x0 , yx0 = b where x0 ∈ {0, 1}(1/2) log s and b ∈ {0, 1}.
The function takes the value b everywhere in V . Also, if the address bits x and the bit yx0 are set to other
values than x0 and b, then the restricted functions in the respective affine subspaces are all constants (if
x is set to x0 ) or dictators (on the addressed bits). The subsequent steps query different dictators on the
addressed bits.
The address function clearly satisfies Conjecture 1.4, and all the intermediate functions that are
given rise to by NA DT are dictators, which also trivially satisfy the conjecture. Thus this rules out the
possibility of refuting Conjecture 1.4 by analyzing NA DT assuming the conjecture. We note, however,
that if we assume the conjecture, then we can improve the upper bound by a factor of O(log s), to the
√
optimal O( s).
Acknowledgements
I thank Avishay Tal for observing that an earlier analysis of NA DT which proved a O(s2/3 ) upper bound
√
can be tightened to obtain the O( s log s) upper bound, and bringing it to my notice. I thank the anony-
mous referees for pointing out that Theorem 1.2 implies the existence of simultaneous communication
protocols for XOR functions, for suggesting simplifications of some proofs, and for suggestions that
helped to improve the presentation. I thank Arkadev Chattopadhyay and Prahladh Harsha for many
helpful discussions. I thank Prahladh Harsha for his help in significantly improving the presentation of
this article.
References
[1] S RINIVASAN A RUNACHALAM , S OURAV C HAKRABORTY, T ROY L EE , M ANASWI PARAASHAR ,
AND RONALD DE W OLF : Two new results about quantum exact learning. In Proc. 46th Internat.
Colloq. on Automata, Languages and Programming (ICALP’19), pp. 16:1–16:15. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.16, arXiv:1810.00481]
2
[2] A RKADEV C HATTOPADHYAY, N IKHIL S. M ANDE , AND S UHAIL S HERIF: The log-
approximate-rank conjecture is false. In Proc. 50th STOC, pp. 42–53. ACM Press, 2019.
[doi:10.1145/3313276.3316353] 4
[3] D MITRY G AVINSKY, NAOMI K IRSHNER , A LEX S AMORODNITSKY, AND RONALD DE W OLF:
Private communication, 2014. 3
[4] PARIKSHIT G OPALAN , RYAN O’D ONNELL , ROCCO A. S ERVEDIO , A MIR S HPILKA , AND K ARL
W IMMER: Testing Fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075–1100, 2011.
Preliminary version in ICALP’09. [doi:10.1137/100785429] 2, 3, 6
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 11
S WAGATO S ANYAL
[5] T OM G UR AND O MER TAMUZ: Testing Booleanity and the uncertainty principle. Chicago J.
Theoret. Computer Sci., 2013(14), 2013. [doi:10.4086/cjtcs.2013.014, arXiv:1204.0944] 6
[6] H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT: Structure of protocols for
XOR functions. SIAM J. Comput., 47(1):208–217, 2018. Preliminary version in FOCS’16.
[doi:10.1137/17M1136869] 5
[7] I SHAY H AVIV AND O DED R EGEV: The list-decoding size of Fourier-sparse Boolean func-
tions. ACM Trans. Comput. Theory, 8(3):10:1–10:14, 2016. Preliminary version in CCC’15.
[doi:10.1145/2898439, arXiv:1504.01649] 2
[8] S AMPATH K ANNAN , E LCHANAN M OSSEL , S WAGATO S ANYAL , AND G RIGORY YAROSLAVTSEV:
Linear sketching over F2 . In Proc. 33rd Computational Complexity Conf. (CCC’18), pp. 8:1–
8:37. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.8,
arXiv:1611.01879] 2
[9] A NDREI V YACHESLAVOVICH K HALYAVIN , M IKHAIL S ERGEEVICH L OBANOV, AND Y URIY VA -
LERIEVICH TARANNIKOV : On plateaued Boolean functions with the same spectrum support. Sib.
Èlektron. Mat. Izv., 13:1346–1368, 2016. [doi:10.17377/semi.2016.13.105] 2
[10] S HACHAR L OVETT: Communication is bounded by root of rank. J. ACM, 63(1):1:1–1:9, 2016.
Preliminary version in STOC’14. [doi:10.1145/2724704, arXiv:1306.1877] 4, 5
[11] A SHLEY M ONTANARO AND T OBIAS O SBORNE: On the communication complexity of XOR
functions, 2009. [arXiv:0909.3392] 5
[12] S WAGATO S ANYAL: Near-optimal upper bound on Fourier dimension of Boolean functions in terms
of Fourier sparsity. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming
(ICALP’15), pp. 1035–1045. Springer, 2015. [doi:10.1007/978-3-662-47672-7_84] 1
[13] A MIR S HPILKA , AVISHAY TAL , AND B EN LEE VOLK: On the structure of Boolean functions with
small spectral norm. Comput. Complexity, 26(1):229–273, 2017. Preliminary version in ITCS’14.
[doi:10.1145/2591796.2591799, arXiv:1304.0371] 3, 4
[14] H ING Y IN T SANG , C HUNG H OI W ONG , N ING X IE , AND S HENGYU Z HANG: Fourier sparsity,
spectral norm, and the Log-rank Conjecture. In Proc. 54th FOCS, pp. 658–667. IEEE Comp. Soc.
Press, 2013. [doi:10.1109/FOCS.2013.76, arXiv:1304.1245] 3, 4, 5, 6
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 12
F OURIER S PARSITY AND D IMENSION
AUTHOR
Swagato Sanyal
Assistant professor
Department of Computer Science and Engineering
Indian Institute of Technology, Kharagpur
India
swagato cs iitkgp ac in
http://cse.iitkgp.ac.in/~swagato/
ABOUT THE AUTHOR
S WAGATO S ANYAL graduated from the Tata Institute of Fundamental Research, Mumbai,
India in 2017; his advisor was Prahladh Harsha. The subject of his thesis was analysis of
Boolean functions and query complexity. The work presented in this paper was done as
part of his Ph. D. dissertation.
T HEORY OF C OMPUTING, Volume 15 (11), 2019, pp. 1–13 13