Linear Sketching over F2
Sampath Kannan

∗

Elchanan Mossel

†

Grigory Yaroslavtsev

‡

arXiv:1611.01879v2 [] 11 Nov 2016

November 14, 2016

Abstract
We initiate a systematic study of linear sketching over F2 . For a given Boolean function
f : {0, 1}n → {0, 1} a randomized F2 -sketch is a distribution M over d×n matrices with elements
over F2 such that Mx suffices for computing f (x) with high probability. We study a connection
between F2 -sketching and a two-player one-way communication game for the corresponding
XOR-function. Our results show that this communication game characterizes F2 -sketching under
the uniform distribution (up to dependence on error). Implications of this result include: 1)
a composition theorem for F2 -sketching complexity of a recursive majority function, 2) a tight
relationship between F2 -sketching complexity and Fourier sparsity, 3) lower bounds for a certain
subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne
regarding one-way communication complexity of linear threshold functions by designing an F2 sketch of optimal size.
Furthermore, we show that (non-uniform) streaming algorithms that have to process random
updates over F2 can be constructed as F2 -sketches for the uniform distribution with only a minor
loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC’14) who show an
analogous result for linear sketches over integers in the adversarial setting our result doesn’t
require the stream length to be triply exponential in n and holds for streams of length Õ(n)
constructed through uniformly random updates. Finally, we state a conjecture that asks whether
optimal one-way communication protocols for XOR-functions can be constructed as F2 -sketches
with only a small loss.

∗

University of Pennsylvania, kannan@cis.upenn.edu
Massachusetts Institute of Technology, elmos@mit.edu. E.M. acknowledges the support of grant N00014-16-12227 from Office of Naval Research and of NSF award CCF 1320105 as well as support from Simons Think Tank on
Geometry & Algorithms.
‡
Indiana University, Bloomington grigory@grigory.us
†

Contents
1 Introduction

1

2 Preliminaries
2.1 Communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Fourier analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
6
6

3 F2 -sketching over the uniform distribution

7

4 Applications
13
4.1 Composition theorem for majority . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Address function and Fourier sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Symmetric functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Turnstile streaming algorithms over F2
19
5.1 Random streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Adversarial streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Linear threshold functions

21

7 Towards the proof of Conjecture 1.3

23

Appendix

29

A Deterministic F2 -sketching
29
A.1 Disperser argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
A.2 Composition and convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
B Randomized F2 -sketching
30
B.1 Extractor argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
B.2 Existential lower bound for arbitrary distributions . . . . . . . . . . . . . . . . . . . 32
B.3 Random F2 -sketching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
C Tightness of Theorem 3.4 for the Majority function

33

1

Introduction

Linear sketching is the underlying technique behind many of the biggest algorithmic breakthroughs
of the past two decades. It has played a key role in the development of streaming algorithms
since [AMS99]and most recently has been the key to modern randomized algorithms for numerical
linear algebra (see survey [Woo14]), graph compression (see survey [McG14]), dimensionality reduction, etc. Linear sketching is robust to the choice of a computational model and can be applied in
settings as seemingly diverse as streaming, MapReduce as well as various other distributed models
of computation [HPP+ 15], allowing to save computational time, space and reduce communication
in distributed settings. This remarkable versatility is based on properties of linear sketches enabled by linearity: simple and fast updates and mergeability of sketches computed on distributed
data. Compatibility with fast numerical linear algebra packages makes linear sketching particularly
attractive for applications.
Even more surprisingly linear sketching over the reals is known to be the best possible algorithmic approach (unconditionally) in certain settings. Most notably, under some mild conditions
linear sketches are known to be almost space optimal for processing dynamic data streams [Gan08,
LNW14, AHLW16]. Optimal bounds for streaming algorithms for a variety of computational
problems can be derived through this connection by analyzing linear sketches rather than general algorithms. Examples include approximate matchings [AKLY16], additive norm approximation [AHLW16] and frequency moments [LNW14].
In this paper we study the power of linear sketching over F2 . 1 To the best of our knowledge no
such systematic study currently exists as prior work focuses on sketching over the field of reals (or
large finite fields as reals are represented as word-size bounded integers). Formally, given a function
f : {0, 1}n → {0, 1} that needs to be evaluated over an input x = (x1 , . . . , xn ) we are looking for
a distribution over k subsets S1 , . . . , Sk ⊆ [n] such that the following holds: for any input x given
parities computed over these sets and denoted as χS1 (x), χS2 (x), . . . , χSk (x)2 it should be possible
to compute f (x) with probability 1 − δ. In the matrix form sketching corresponds to multiplication
over F2 of the row vector x by a random n × k matrix whose i-th column is a characteristic vector
of the random parity χSi :
 .
..
..
.. 
..
.
.
.
 


x1 x2 . . . xn  χS1 χS2 . . . χSk  = χS1 (x) χS2 (x) . . . χSk (x)
..
..
..
..
.
.
.
.

This sketch alone should then be sufficient for computing f with high probability for any input x.
This motivates us to define the randomized linear sketch complexity of a function f over F2 as the
smallest k which allows to satisfy the above guarantee.
Definition 1.1 (F2 -sketching). For a function f : Fn2 → F2 we define its randomized linear sketch
complexity3 over F2 with error δ (denoted as Rδlin (f )) as the smallest integer k such that there
1

It is easy to see that sketching over finite fields can be significantly better than linear sketching over integers for
certain computations. As an example, consider a function (x mod 2) (for an integer input x) which can be trivially
sketched with 1 bit over the field of two elements while any linear sketch over the integers requires word-size memory.
2
Here we use notation χS (x) = ⊕i∈S xi .
3
In the language of decision trees this can be interpreted as randomized non-adaptive parity decision tree complexity. We are unaware of any systematic study of this quantity either. Since heavy decision tree terminology seems
excessive for our applications (in particular, sketching is done in one shot so there isn’t a decision tree involved) we
prefer to use a shorter and more descriptive name.

1

exists a distribution χS1 , χS2 , . . . , χSk over k linear functions over F2 and a postprocessing function
g : Fk2 → F2 4 which satisfies:
∀x ∈ Fn2 :

Pr [f (x1 , x2 , . . . , xn ) = g(χS1 (x), χS2 (x), . . . , χSk (x))] ≥ 1 − δ.

S1 ,...,Sk

As we show in this paper the study of Rδlin (f ) is closely related to a certain communication
complexity problem. For f : Fn2 → F2 define the XOR-function f + : Fn2 × Fn2 → F2 as f + (x, y) =
f (x + y) where x, y ∈ Fn2 . Consider a communication game between two players Alice and Bob
holding inputs x and y respectively. Given access to a shared source of random bits Alice has to
send a single message to Bob so that he can compute f + (x, y). This is known as the one-way
communication complexity problem for XOR-functions.
Definition 1.2 (Randomized one-way communication complexity of XOR function). For a function f : Fn2 → F2 the randomized one-way communication complexity with error δ (denoted as
Rδ→ (f + )) of its XOR-function is defined as the smallest size5 (in bits) of the (randomized using
public randomness) message M (x) from Alice to Bob which allows Bob to evaluate f + (x, y) for any
x, y ∈ Fn2 with error probability at most δ.
Communication complexity complexity of XOR-functions has been recently studied extensively
in the context of the log-rank conjecture (see e.g. [SZ08, ZS10, MO09, LZ10, LLZ11, SW12, LZ13,
TWXZ13, Lov14, HHL16]). However, such studies either mostly focus on deterministic communication complexity or are specific to the two-way communication model. We discuss implications of
this line of work for our F2 -sketching model in our discussion of prior work.
It is easy to see that Rδ→ (f + ) ≤ Rδlin (f ) as using shared randomness Alice can just send k bits
χS1 (x), χS2 (x), . . . , χSk (x) to Bob who can for each i ∈ [k] compute χSi (x + y) = χSi (x) + χSi (y),
which is an F2 -sketch of f on x + y and hence suffices for computing f + (x, y) with probability
1 − δ. The main open question raised in our work is whether the reverse inequality holds (at least
approximately), thus implying the equivalence of the two notions.

Conjecture 1.3. Is it true that Rδ→ (f + ) = Θ̃ Rδlin (f ) for every f : Fn2 → F2 and 0 < δ < 1/2?

In fact all known one-way protocols for XOR-functions can be seen as F2 -sketches so it is natural
to ask whether this is always true. In this paper we further motivate this conjecture through a
number of examples of classes of functions for which it holds. One important such example from the
previous work is a function Ham≥k which evaluates to 1 if and only if the Hamming weight of the
input string is at least k. The corresponding XOR-function Ham+
≥k can be seen to have one-way
communication complexity of Θ(k log k) via the small set disjointness lower bound of [DKS12] and
a basic upper bound based on random parities [HSZZ06]. Conjecture 1.3 would imply that in order
to prove a one-way disjointness lower bound it suffices to only consider F2 -sketches.
In the discussion below using Yao’s principle we switch to the equivalent notion of distributional
complexity of the above problems denoted as Dδ→ and Dδlin respectively. For the formal definitions
we refer to the reader to Section 2.1 and a standard textbook on communication complexity [KN97].
4

If a random family of functions is used here then the definition is changed accordingly. In this paper all g are
deterministic.
5
Formally the minimum here is taken over all possible protocols where for each protocol the size of the message
M (x) refers to the largest size (in bits) of such message taken over all inputs x ∈ Fn
2 . See [KN97] for a formal
definition.

2

Equivalence between randomized and distributional complexities allows us to restate Conjecture 1.3
as Dδ→ = Θ̃(Dδlin ).
For a fixed distribution µ over Fn2 we define Dδlin,µ (f ) to be the smallest dimension of an F2 sketch that correctly outputs f with probability 1 − δ over µ. Similarly for a distribution µ over
(x, y) ∈ Fn2 × Fn2 we denote distributional one-way communication complexity of f with error δ as
Dδ→,µ(f + ) (See Section 2 for a formal definition). Our first main result is an analog of Conjecture 1.3
for the uniform distribution U over (x, y) that matches the statement of the conjecture up to
dependence on the error probability:
lin,U
→,U
+
(f ).
Theorem 1.4. For any f : Fn2 → F2 it holds that DΘ(
1 (f ) ≥ D 1
)
n

3

A deterministic analog of Definition 1.1 requires that f (x) = g(χα1 (x), χα2 (x), . . . , χαk (x)) for a
fixed choice of α1 , . . . , αk ∈ Fn2 . The smallest value of k which satisfies this definition is known to be
equal to the Fourier dimension of f denoted as dim(f ). It corresponds to the smallest dimension
of a linear subspace of Fn2 that contains the entire spectrum of f (see Section 2.2 for a formal
definition). In order to keep the notation uniform we also denote it as D lin (f ). Most importantly,
as shown in [MO09] an analog of Conjecture 1.3 holds without any loss in the deterministic case,
i.e. D → (f + ) = dim(f ) = D lin (f ), where D → denotes the deterministic one-way communication
complexity. This striking fact is one of the reasons why we suggest Conjecture 1.3 as an open
problem.
In order to prove Theorem 1.4 we introduce a notion of an approximate Fourier dimension
(Definition 3.2) that extends the definition of exact Fourier dimension to allow that only 1 − ǫ
fraction of the total “energy” in f ’s spectrum should be contained in the linear subspace. The key
ingredient in the proof is a structural theorem Theorem 3.4 that characterizes both Dδlin,U (f ) and
Dδ→,U (f + ) in terms of f ’s approximate Fourier dimension.

Previous work and our results
Using Theorem 3.4 we derive a number of results that confirm Conjecture 1.3 for specific classes of
functions.
Recursive majority For an odd integer n the majority function M ajn is defined as to be equal
1 if and only if the Hamming weight of the input is greater than n/2. Of particular interest is
the recursive majority function M aj3◦k that corresponds to k-fold composition of M aj3 for k =
log3 n. This function was introduced by Boppana [SW86] and serves as an important example of
various properties of Boolean functions, most importantly in randomized decision tree complexity
([SW86, JKS03, MNSX11, Leo13, MNS+ 13]) and most recently deterministic parity decision tree
complexity [BTW15].
In Section 4.1 we show to use Theorem 3.4 to obtain the following result:
Theorem 1.5. For any ǫ ∈ [0, 1], γ <

1
2

− ǫ and k = log3 n it holds that:
+

D →,U
(M aj3◦k ) ≥ ǫ2 n + 1.
1 1
−ǫ2 )
n(4
In particular, this confirms Conjecture 1.3 for M aj3◦k with at most logarithmic gap as for
+
→,U
◦k + ) = Ω(n). By Yao’s principle R→
(M aj3◦k ) = Ω(n). Using
constant ǫ we get DΘ(
1 (M aj3
Θ( 1 )
)
n

n

3

+

standard error reduction [KN97] for randomized communication this implies that Rδ→ (M aj3◦k ) =
Ω̃(n) for constant δ < 1/2 almost matching the trivial upper bound.
Address function and Fourier sparsity The number s of non-zero Fourier coefficients of f
(known as Fourier sparsity) is one of the key quantities in the analysis of Boolean functions. It also
plays an important role in the recent work on log-rank conjecture for XOR-functions [TWXZ13,
STlV14]. A remarkable recent result by Sanyal [San15] shows that for Boolean functions dim(f ) =
√
O( s log s), namely all non-zero Fourier coefficients are contained in a subspace of a polynomially
smaller dimension. This bound is almost tight as the address function (see Section 4.2 for a
definition) exhibits a quadratic gap. A direct implication of Sanyal’s result is a deterministic F2 √
sketching upper bound of O( s log s) for any f with Fourier sparsity s. As we show in Section 4.2
this dependence on sparsity can’t be improved even if randomization is allowed.
Symmetric functions A function f is symmetric if it only depends on the Hamming weight of
its input. In Section 4.3 we show that Conjecture 1.3 holds (approximately)
for symmetric functions
P
which are not too close to a constant function or the parity function i xi where the sum is taken
over F2 .
Applications to streaming In the turnstile streaming model of computation an vector x of
dimension n is updated through a sequence of additive updates applied to its coordinates and the
goal of the algorithm is to be able to output f (x) at any point during the stream while using space
that is sublinear in n. In the real-valued case we have either x ∈ [0, m]n or x ∈ [−m, m]n for
some universal upper bound m and updates can be increments or decrements to x’s coordinates of
arbitrary magnitude.
For x ∈ Fn2 additive updates have a particularly simple form as they always flip the corresponding
coordinate of x. As we show in Section 5.2 it is easy to see based on the recent work of [Gan08,
LNW14, AHLW16] that in the adversarial streaming setting the space complexity of turnstile
streaming algorithms over F2 is determined by the F2 -sketch complexity of the function of interest.
However, this proof technique only works for very long streams which are unrealistic in practice
– the length of the adversarial stream has to be triply exponential in n in order to enforce linear
behavior. Large stream length requirement is inherent in the proof structure in this line of work
and while one might expect to improve triply exponential dependence on n at least an exponential
dependence appears necessary, which is a major limitation of this approach.
As we show in Section 5.1 it follows directly from our Theorem 1.4 that turnstile streaming algorithms that achieve low error probability under random F2 updates might as well be F2 -sketches. For
two natural choices of the random update model short streams of length either O(n) or O(n log n)
suffice for our reduction. We stress that our lower bounds are also stronger than the worst-case
adversarial lower bounds as they hold under an average-case scenario. Furthermore, our Conjecture 1.3 would imply that space optimal turnstile streaming algorithms over F2 have to be linear
sketches for adversarial streams of length only 2n.
Linear Threshold Functions Linear threshold functions (LTFs) are one of the most studied
classes of Boolean functions as they play a central role in circuit complexity, learning theory and
machine learning (See Chapter 5 in [O’D14] for a comprehensive introduction to properties of
LTFs). Such functions are parameterized by two parameters θ and m known as threshold and
4

margin respectively (See Definition 6.1 for a formal definition). We design an F2 -sketch for LTFs
with complexity O(θ/m log(θ/m)). By applying the sketch in the one-way communication setting
this fully resolves an open problem posed in [MO09]. Our work shows that dependence on n is
not necessary which is an improvement over previously best known protocol due to [LZ13] which
achieves communication O(θ/m log n). Our communication bound is optimal due to [DKS12]. See
Section 6 for details.
Other previous work Closely related to ours is work on communication protocols for XORfunctions started in [SZ08, MO09]. In particular [MO09] presents two basic one-way communication
protocols based on random parities. First one, stated as Fact B.7 generalizes the classic protocol
for equality. Second one uses the result of Grolmusz [Gro97] and implies that ℓ1 -sampling of Fourier
characters gives a randomized F2 -sketch of size O(kfˆk21 ) (for constant error). Another line of work
that is closely related to ours is the study of the two-player simultaneous message passing model
(SMP). This model can also allow to prove lower bounds on F2 -sketching complexity. However,
in the context of our work there is no substantial difference as for product distributions the two
models are essentially equivalent. Recent results in the SMP model include [MO09, LLZ11, LZ13].
While decision tree literature is not directly relevant to us since our model doesn’t allow adaptivity we remark that there has been interest recently in the study of (adaptive) deterministic parity
decision trees [BTW15] and non-adaptive deterministic parity decision trees [STlV14, San15]. As
mentioned above, our model can be interpreted as non-adaptive randomized parity decision trees
and to the best of our knowledge it hasn’t been studied explicitly before. Another related model
is that of parity kill numbers. In this model a composition theorem has recently been shown
by [OWZ+ 14] but the key difference is again adaptivity.
Organization The rest of this paper is organized as follows. In Section 2 we introduce the
required background from communication complexity and Fourier analysis of Boolean functions.
In Section 3 we prove Theorem 1.4. In Section 4 we give applications of this theorem for recursive
majority (Theorem 1.5), address function and symmetric functions. In Section 5 we describe
applications to streaming. In Section 6 we describe our F2 -sketching protocol for LTFs. In Section 7
we show a lower bound for one-bit protocols making progress towards resolving Conjecture 1.3.
In Appendix A we give some basic results about deterministic F2 -sketching (or Fourier dimension) of composition and convolution of functions. We also present a basic lower bound argument
based on affine dispersers. In Appendix B we give some basic results about randomized F2 -sketching
including a lower bound based on extractors and a classic protocol based on random parities which
we use as a building block in our sketch for LTFs. We also present evidence for why an analog of
Theorem 3.4 doesn’t hold for arbitrary distributions. In Appendix C we argue that the parameters
of Theorem 3.4 can’t be substantially improved.

2

Preliminaries

For an integer n we use notation [n] = {1, . . . , n}. For integers n ≤ m we use notation [n, m] =
{n, . . . , m}. For an arbitrary domain D we denote the uniform distribution over this domain as
U (D). For a vector x and p ≥ 1 we denote the p-norm of x as kxkp and reserve the notation kxk0
for the Hamming weight.

5

2.1

Communication complexity

Consider a function f : Fn2 × Fn2 → F2 and a distribution µ over Fn2 × Fn2 . The one-way distributional
complexity of f with respect to µ, denoted as Dδ→,µ (f ) is the smallest communication cost of
a one-way deterministic protocol that outputs f (x, y) with probability at least 1 − δ over the
inputs (x, y) drawn from the distribution µ. The one-way distributional complexity of f denoted
as Dδ→ (f ) is defined as Dδ→ (f ) = supµ Dδ→,µ(f ). By Yao’s minimax theorem [Yao83] it follows
that Rδ→ (f ) = Dδ→ (f ). One-way communication complexity over product distributions is defined as
Dδ→,× (f ) = supµ=µx ×µy Dδ→,µ(f ) where µx and µy are distributions over Fn2 .
With every two-party function f : Fn2 × Fn2 we associate with it the communication matrix
n
n
f
= f (x, y). We say that a deterministic protocol M (x) with length
M f ∈ F22 ×2 with entries Mx,y
t of the message that Alice sends to Bob partitions the rows of this matrix into 2t combinatorial
rectangles where each rectangle contains all rows of M f corresponding to the same fixed message
y ∈ {0, 1}t .

2.2

Fourier analysis

We consider functions from Fn2 to 6 . For any fixed n ≥ 1, the space of these
P functions forms an
1
inner product space with the inner product hf, gi = x∈F n2 [f (x)g(x)] = 2n x∈F n f (x)g(x). The ℓ2
2
p
p
2
norm of f : Fn2 → is kf k2 = hf, f i =
x [f (x) ] and the ℓ2 distance between
p two functions
n →
hf − g, f − gi =
is
the
ℓ
norm
of
the
function
f
−
g.
In
other
words,
kf
−
gk
=
f, g : F
2
2
q2 P
1
√ n
(f (x) − g(x))2 .
x∈F n
2
|F 2 |
P
For x, y ∈ Fn2 we denote the inner product as x · y = ni=1 xi yi . For α ∈ Fn2 , the character
χα : Fn2 → {+1, −1} is the function defined by χα (x) = (−1)α·x . Characters form an orthonormal
basis as hχα , χβ i = δαβ where δ is the Kronecker symbol. The Fourier coefficient of f : Fn2 →
corresponding to α is fˆ(α) = x [f (x)χα (x)]. The Fourier transform of f is the function fˆ : Fn2 →
that returns the value of each Fourier coefficient of f . We use notation Spec(f ) = {α ∈ Fn2 : fˆ(α) 6=
0} to denote the set of all non-zero Fourier coefficients of f .
The set of Fourier transforms of functions mapping Fn2 →
forms an inner product
rD space
E
D
E P
fˆ, fˆ =
with inner product fˆ, ĝ = α∈F n fˆ(α)ĝ(α). The corresponding ℓ2 norm is kfˆk2 =
2
qP
fˆ(α)2 . Note that the inner product and ℓ2 norm are weighted differently for a function
α∈F n
2
f : Fn → and its Fourier transform fˆ : Fn → .
2

2

Fact 2.1 (Parseval’s identity). For any f : Fn2 → it holds that kf k2 = kfˆk2 =
Moreover, if f : Fn → {+1, −1} then kf k2 = kfˆk2 = 1.
2

qP

α∈F n
2

fˆ(α)2 .

We use notation A ≤ Fn2 to denote the fact that A is a linear subspace of Fn2 .
Definition 2.2 (Fourier dimension). The Fourier dimension of f : Fn2 → {+1, −1} denoted as
dim(f ) is the smallest integer k such that there exists A ≤ Fn2 of dimension k for which Spec(f ) ⊆
A.
6

In all Fourier-analytic arguments Boolean functions are treated as functions of the form f : Fn
2 → {+1, −1}
where 0 is mapped to 1 and 1 is mapped to −1. Otherwise we use these two notations interchangeably.

6

We say that A ≤ Fn2 is a standard subspace if it has a basis v1 , . . . , vd where each vi has Hamming
weight equal to 1. An orthogonal subspace A⊥ is defined as:
A⊥ = {γ ∈ Fn2 : ∀x ∈ A γ · x = 0}.
An affine subspace (or coset) of Fn2 of the form A = H + a for some H ≤ Fn2 and a ∈ Fn2 is defined
as:
A = {γ ∈ Fn2 : ∀x ∈ H ⊥

γ · x = a · x}.

We now introduce notation for restrictions of functions to affine subspaces.
Definition 2.3. Let f : Fn2 →

and z ∈ Fn2 . We define f +z : Fn2 →

as f +z (x) = f (x + z).

+z (γ) = (−1)γ·z fˆ(γ) and hence:
Fact 2.4. Fourier coefficients of f +z are given as fd
X
f +z =
fˆ(S)χS (z)χS .
S∈F n
2

+z
:H→
Definition 2.5 (Coset restriction). For f : Fn2 → , z ∈ Fn2 and H ≤ Fn2 we write fH
the restriction of f to H + z.

Definition 2.6 (Convolution). For two functions f, g : Fn2 →
is defined as (f ∗ g)(x) = y∼U (F n2 ) [f (x)g(x + y)].

for

their convolution (f ∗ g) : Fn2 →

∗ g(S) = fˆ(S)ĝ(S).
For S ∈ Fn2 the corresponding Fourier coefficient of convolution is given as f[

3

F2-sketching over the uniform distribution

We use the following definition of Fourier concentration that plays an important role in learning
theory [KM93].
Definition 3.1 (Fourier concentration). The spectrum of aPfunction f : Fn2 → {+1, −1} is ǫconcentrated on a collection of Fourier coefficients Z ⊆ Fn2 if S∈Z fˆ2 (S) ≥ ǫ.

For a function f : Fn2 → {+1, −1} and a parameter ǫ > 0 we introduce a notion of approximate
Fourier dimension as the smallest integer for which f is ǫ-concentrated on some linear subspace of
dimension d.

Definition 3.2 (Approximate Fourier dimension). Let Ak be the set of all linear subspaces of Fn2
of dimension k. For f : Fn2 → {+1, −1} and ǫ > 0 the approximate Fourier dimension dimǫ (f ) is
defined as:
)
(
X
dimǫ (f ) = min ∃A ∈ Ak :
fˆ(S)2 ≥ ǫ .
k

S∈A

Definition 3.3 (Approximate Fourier dimension gap). For f : Fn2 → {+1, −1} and 1 ≤ d ≤ n we
define:
ǫd (f ) = max {dimǫ (f ) = d} ,

∆d (f ) = ǫd (f ) − ǫd−1 (f ),

ǫ

where we refer to ∆d (f ) as the approximate Fourier dimension gap of dimension d.
7

The following theorem shows that (up to some slack in the dependence on the probability of
error) the one-way communication complexity under the uniform distribution matches the linear
sketch complexity. We note that the theorem can be applied to all possible values of d and show
how to pick specific values of d of interest in Corollary 3.10. We illustrate tightness of Part 3 of this
theorem in Appendix C. We also note that the lower bounds given by this theorem are stronger
than the basic extractor lower bound given in Appendix B.1. See Remark B.5 for further discussion.
Theorem 3.4. For any f : Fn2 → {+1, −1}, 1 ≤ d ≤ n and ǫ1 = ǫd (f ), γ <
1.

→,U
lin,U
D(1−ǫ
(f + ) ≤ D(1−ǫ
(f ) ≤ d,
1 )/2
1 )/2

2.

Dγlin,U (f ) ≥ d + 1,

√
1− ǫ1
2 ,

3.

δ = ∆d (f )/4:

Dδ→,U (f + ) ≥ d.

Proof. Part 17 . By the assumptions
P of the theorem we know that there exists a d-dimensional
subspace A ≤ Fn2 which satisfies S∈A fˆ2 (S) ≥ ǫ1 . Let g : Fn2 → be a function defined by its
Fourier transform as follows:
(
fˆ(S), if S ∈ A
ĝ(S) =
0, otherwise.
Consider drawing a random variable θ from the distribution with p.d.f 1 − |θ| over [−1, 1].
Proposition 3.5. For all t such that −1 ≤ t ≤ 1 and z ∈ {+1, −1} random variable θ satisfies:
1
Pr[sgn(t − θ) 6= z] ≤ (z − t)2 .
θ
2
Proof. W.l.o.g we can assume z = 1 as the case z = −1 is symmetric. Then we have:
Z 1
Z 1
1
(1 − γ)dγ = (1 − t)2 .
(1 − |γ|)dγ ≤
Pr[sgn(t − θ) 6= 1] =
θ
2
t
t
Define a family of functions gθ : Fn2 → {+1, −1} as gθ (x) = sgn(g(x) − θ). Then we have:




Pr[gθ (x) 6= f (x)]
Pr [gθ (x) 6= f (x)] =
θ
x∼F n
θ x∼F n
2
2


=
Pr[sgn(g(x) − θ) 6= f (x)]
θ
x∼F n
2


1
2
(f (x) − g(x)) (by Proposition 3.5)
≤
2
x∼F n
2
1
= kf − gk22 .
2
Using the definition of g and Parseval we have:
1 − ǫ1
1
1
1 X ˆ2
1
f (S) ≤
kf − gk22 = kf[
− gk22 = kfˆ − ĝk22 =
.
2
2
2
2
2
S ∈A
/

1
Thus, there exists a choice of θ such that gθ achieves error at most 1−ǫ
2 . Clearly gθ can be computed
lin,U
based on the d parities forming a basis for A and hence D(1−ǫ1 )/2 (f ) ≤ d.
7

This argument is a refinement of the standard “sign trick” from learning theory which approximates a Boolean
function by taking a sign of its real-valued approximation under ℓ2 .

8

Part 2. Fix any deterministic sketch that uses d functions χS1 , . . . , χSd and let S = (S1 , . . . , Sd ).
For fixed values of these sketches b = (b1 , . . . , bd ) where bi = χSi (x) we denote the restriction on
the resulting coset as f |(S,b) . Using the standard expression for the Fourier coefficients of an affine
restriction the constant Fourier coefficient of the restricted function is given as:
!
P
X
X
b
f\
|(S,b) (∅) =
(−1) i∈Z i fˆ
Si .
i∈Z

Z⊆[d]

Thus, we have:
f\
|(S,b) (∅)2 =

X

Z⊆[d]

X
fˆ2 (
Si ) +
i∈Z

X

P

(−1)

i∈Z1 ∆Z2 bi

fˆ(

X

i∈Z1

Z1 6=Z2 ⊆[d]

Si )fˆ(

X

Si ).

i∈Z2

Taking expectation over a uniformly random b ∼ U (Fd2 ) we have:

 


!
i
h
P
X
X
X
X
X
b
\ 2 =

Si  fˆ 
Si 
(−1) i∈Z1 ∆Z2 i fˆ 
Si +
fˆ2
b∼U (F d ) f |(S,b) (∅)
b∼U (F d )
2

2

Z⊆[d]

=

X

fˆ2

X

Si

i∈Z

Z⊆[d]

!

i∈Z

Z1 6=Z2 ⊆[d]

i∈Z1

i∈Z2

.

The latter sum is the sum of squared Fourier coefficients over a linear subspace of dimension d
and hence is at most ǫ1 by the assumption of the theorem. Using Jensen’s inequality:
h
i r
h
i √
\
\
2 ≤
|
f
|
(∅)|
≤
ǫ1 .
f
|
(∅)
d
d
(S,b)
(S,b)
b∼U (F )
b∼U (F )
2

2

For a fixed restriction (S, b) if |fˆ|(S,b) (∅)| ≤ α then |P r[f |(S,b) = 1] − P r[f |(S,b) = −1]| ≤ α and
hence no algorithm can predict the value of the restricted function on this coset with probability
greater than 1+α
2 . Thus no algorithm can predict f |(S1 ,b1 ),...,(Sd ,bd ) for a uniformly random choice of

(b1 , . . . , bd ) and hence also on a uniformly at random chosen x with probability greater than
Part 3.

√
1+ ǫ1
2 .

Let ǫ2 = ǫd−1 (f ) and recall that ǫ1 = ǫd (f ).

Definition 3.6. We say that A ≤ Fn2 distinguishes x1 , x2 ∈ Fn2 if ∃S ∈ A : χS (x1 ) 6= χS (x2 ).
We first prove the following auxiliary lemma.
Lemma 3.7. Fix ǫ1 > ǫ2 ≥ 0 and x1 , x2 ∈ Fn2 . If there exists a subspace Ad ≤ Fn2 of dimension
d which distinguishes x1 and x2 such that f : Fn2 → {+1, −1} is ǫ1 -concentrated on Ad but is not
ǫ2 -concentrated on any d − 1 dimensional linear subspace then:
Pr [f +x1 (z) 6= f +x2 (z)] ≥ ǫ1 − ǫ2 .

z∈U (F n
2)

Proof. Note that for a fixed x ∈ Fn2 (by Fact 2.4) the Fourier expansion of f +x can be given as:
X
X
f +x (z) =
fˆ(S)χS (z + x) =
fˆ(S)χS (z)χS (x).
S∈F n
2

S∈F n
2

9

Thus we have:

1
1 − hf +x1 , f +x2 i
2

+
*
X
X
1
fˆ(S1 )χS1 χS1 (x1 ),
fˆ(S2 )χS2 χS2 (x2 ) 
1−
=
2
S1 ∈F n
S2 ∈F n
2
2


X
1
fˆ(S)2 χS (x1 )χS (x2 ) (by orthogonality of characters)
= 1 −
2
n

Pr n [f +x1 (z) 6= f +x2 (z)] =

z∈U (F 2 )

S∈F 2

P
We now analyze the expression S∈F n fˆ(S)2 χS (x1 )χS (x2 ). Breaking the sum into two parts
2
we have:
X
X
X
fˆ(S)2 χS (x1 )χS (x2 ) =
fˆ(S)2 χS (x1 )χS (x2 ) +
fˆ(S)2 χS (x1 )χS (x2 )
S∈F n
2

S∈Ad

≤

X

S∈Ad

S ∈A
/ d

fˆ(S)2 χS (x1 )χS (x2 ) + (1 − ǫ1 ).

To give a bound on the first term we will use the fact that Ad distinguishes x1 and x2 . We will
need the following simple fact.
Proposition 3.8. If Ad distinguishes x1 and x2 then there exists a basis S1 , S2 , . . . , Sd in Ad such
that χS1 (x1 ) 6= χS1 (x2 ) while χSi (x1 ) = χSi (x2 ) for all i ≥ 2.
Proof. Since Ad distinguishes x1 and x2 there exists a S ∈ Ad such that χS (x1 ) 6= χS (x2 ). Fix
S1 = S and consider an arbitrary basis in Ad of the form (S1 , T2 , . . . , Td ). For i ≥ 2 if χTi (x1 ) =
χTi (x2 ) then we let Si = Ti . Otherwise, we let Si = Ti + S1 , which preserves the basis and ensures
that:
χSi (x1 ) = χTi +S1 (x1 ) = χTi (x1 )χS1 (x1 ) = χTi (x1 )χS1 (x2 ) = χSi (x2 ).
Fix the basis (S1 , S2 , . . . , Sd ) in Ad with the properties given by Proposition 3.8. Let Ad−1 =
span(S2 , . . . , Sd ) so that for all S ∈ Ad−1 it holds that χS (x1 ) = χS (x2 ). Then we have:
X
X
X
fˆ(S)2 χS (x1 )χS (x2 ) =
fˆ(S)2 χS (x1 )χS (x2 ) +
fˆ(S + S1 )2 χS+S1 (x1 )χS+S1 (x2 )
S∈Ad

S∈Ad−1

=

X

S∈Ad−1

fˆ(S) −
2

X

S∈Ad−1

S∈Ad−1

fˆ(S + S1 )2

The first term in the above summation is at most ǫ2 since f is not ǫ2 -concentrated on any (d − 1)dimensional linear subspace. The second is at least ǫ1 − ǫ2 since f is ǫ1 -concentrated on Ad .
Thus, putting things together we have that
X
fˆ(S)2 χS (x1 )χS (x2 ) ≤ ǫ2 − (ǫ1 − ǫ2 ) + (1 − ǫ1 ) = 1 − 2(ǫ1 − ǫ2 ).
S∈F n
2

This completes that proof showing that Prz∈U (F n2 ) [f +x1 (z) 6= f +x2 (z)] ≥ ǫ1 − ǫ2 .
10

We are now ready to complete the proof of the third part of Theorem 3.4. We can always
assume that the protocol that Alice uses is deterministic since for randomized protocols one can
fix their randomness to obtain the deterministic protocol with the smallest error. Fix a (d − 1)-bit
deterministic protocol that Alice is using to send a message to Bob. This protocol partitions the
rows of the communication matrix into t = 2d−1 rectangles corresponding to different messages. We
denote the sizes of these rectangles as r1 , . . . , rt and the rectangles themselves as R1 , . . . , Rt ⊆ Fn2
respectively. Let the outcome of the protocol be P (x, y). Then the error is given as:

x,y∼U (F n
2)

t
X
ri
[ [P (x, y) 6= f (x + y)]]
×
2n x∼U (Ri ),y∼U (F n2 )
i=1
X
ri
≥
[ [P (x, y) 6= f (x + y)]] ,
×
2n x∼U (Ri ),y∼U (F n2 )
n−d

[ [P (x, y) 6= f (x + y)]] =

i : ri >2

where we only restricted attention to rectangles of size greater than 2n−d . Our next lemma shows
that in such rectangles the protocol makes a significant error:
Lemma 3.9. If ri > 2n−d then:
x∼U (Ri ),y∼U (F n
2)

[ [P (x, y) 6= f (x + y)]] ≥

1 ri − 2n−d
(ǫ1 − ǫ2 ).
2
ri

Proof. For y ∈ Fn2 let py (Ri ) = min(Prx∼U (Ri ) [f (x + y) = 1], Prx∼U (Ri ) [f (x + y) = −1]). We have:
x∼U (Ri ),y∼U (F n
2)

[ [P (x, y) 6= f (x + y)]] =

y∼U (F n
2 ) x∼U (Ri )

≥

y∼U (F n
2)

≥

y∼U (F n
2)

=
=

y∼U (F n
2)

[ [P (x, y) 6= f (x + y)]]

[py (Ri )]
[py (Ri )(1 − py (Ri ))]




1
Pr
[f (x1 + y) 6= f (x2 + y)]
2 x1 ,x2 ∼U (Ri )
"
#

1
2 x1 ,x2 ∼U (Ri )

y∼U (F n
2)

[ [f (x1 + y) 6= f (x2 + y)]]

Fix a d-dimensional linear subspace Ad such that g is ǫ1 -concentrated on Ad . There are 2n−d
vectors which have the same inner products with all vectors in Ad . Thus with probability at least
ri −2n−d
two random vectors x1 , x2 ∼ U (Ri ) are distinguished by Ad . Conditioning on this event
ri
we have:
"
#
1
[ [f (x1 + y) 6= f (x2 + y)]]
2 x1 ,x2∼U (Ri ) y∼U (F n2 )
≥

1 ri − 2n−d
2
ri

≥

1 ri − 2n−d
(ǫ1 − ǫ2 ),
2
ri

y∼U (F n
2)

[ [f (x1 + y) 6= f (x2 + y)] |Ad distinguishes x1 , x2 ]

where the last inequality follows by Lemma 3.7.
11

Using Lemma 3.9 we have:
x,y∼U (F n
2)

[ [P (x, y) 6= f (x + y)]] ≥

X

ǫ1 − ǫ2
2n+1

i : ri >2n−d



ri − 2n−d


t

ǫ1 − ǫ2 X 
ri − 2n−d −
= n+1 
2
i=1

ǫ1 − ǫ2
2n+1
ǫ1 − ǫ2
,
=
4
≥

where the inequality follows since
non-positive.

Pt

i=1 ri


2n − 2n−1

X

i : ri ≤2n−d




ri − 2n−d 

= 2n , t = 2d−1 and all the terms in the second sum are

An important question that arises when applying Theorem 3.4 is the choice of the value of d.
The following simple corollaries of Theorem 3.4 give one particularly simple way of choosing these
values for any function in such a way that we obtain a non-trivial lower bound for O(1/n)-error.
Corollary 3.10. For any f : Fn2 → {+1, −1} such that fˆ(∅) ≤ θ for some constant θ < 1 there
exists an integer d ≥ 1 such that:
lin,U
→,U
+
(f )
DΘ(
1 (f ) ≥ d ≥ D 1
)
n

3

Proof. We have ǫ0 (f ) < θ and ǫn (f ) = 1. Let d∗ = arg maxnd=1 ∆d (f ) and ∆(f ) = ∆d∗ (f ). Consider
cases:
→,U
+
∗
Case 1. ∆(f ) ≥ 1−θ
3 . By Part 3 of Theorem 3.4 we have that D 1−θ (f ) ≥ d . Furthermore,
12n

lin,U
∗
ǫd∗ (f ) ≥ θ+ǫd∗ (f )−ǫd∗ −1 (f ) = θ+∆(f ) ≥ 13 − 2θ
3 . By Part 1 of Theorem 3.4 we have D 1−θ (f ) ≤ d .
3

Case 2. ∆(f ) < 1−θ
3 . In this case there exists d1 ≥ 1 such that ǫd1 (f ) ∈ [θ1 , θ2 ] where θ1 =
2(1−θ)
1−θ
θ + 3 , θ2 = θ + 3 . By averaging there exists d2 > d1 such that ∆d2 (f ) = ǫd2 (f ) − ǫd2 −1 (f ) ≥
→,U
1−θ2
1
+
n = Θ( n ). Applying Part 3 of Theorem 3.4 we have that DΘ( 1 ) (f ) ≥ d2 . Furthermore, we have

ǫd2 (f ) ≥ θ1 and hence

1−ǫd2 (f )
2

n

≤

1−θ1
2

<

1−θ
3 .

By Part 1 of Theorem 3.4 we have D lin,U
1−θ (f ) ≤ d2 .
3

The proof of Theorem 1.4 follows directly from Corollary 3.10. If θ ≤ 31 then the statement of
(f ) ≤ 0 and
the theorem holds. If θ ≥ 13 then ǫ0 (f ) ≥ 13 so by Part 1 of Theorem 3.4 we have D lin,U
1
3

the inequality holds trivially.
Furthermore, using the same averaging argument as in the proof of Corollary 3.10 we obtain
the following generalization of the above corollary that will be useful for our applications.
Corollary 3.11. For any f : Fn2 → {+1, −1} and d such that ǫd−1 (f ) ≤ θ it holds that:
D →,U
1−θ (f ) ≥ d.
4(n−d)

12

4

Applications

4.1

Composition theorem for majority

In this section using Theorem 3.4 we give a composition theorem for F2 -sketching of the composed
M aj3 function. Unlike in the deterministic case for which the composition theorem is easy to show
(see Lemma A.6) in the randomized case composition results require more work.
mn
Definition 4.1 (Composition). For f : Fn2 → F2 and g : Fm
2 → F2 their composition f ◦g : F2 → F2
is defined as:

(f ◦ g)(x) = f (g(x1 , . . . , xm ), g(xm+1 , . . . , x2m ), . . . , g(xm(n−1)+1 , . . . , xmn )).
Consider the recursive majority function M aj3◦k ≡ M aj3 ◦ M aj3 ◦ · · · ◦ M aj3 where the composition is taken k times.
Theorem 4.2. For any d ≤ n and k = log3 n it holds that ǫd (M aj3◦k ) ≤

4d
n.

First, we show a slighthly stronger result for standard subspaces and then extend this result to
arbitrary subspaces with a loss of a constant factor. Fix any set S ⊆ [n] of variables. We associate
this set with a collection of standard unit vectors corresponding to these variables. Hence in this
notation ∅ corresponds to the all-zero vector.
Lemma 4.3. For any standard subspace whose basis consists of singletons from the set S ⊆ [n] it
holds that:
2 |S|
X 
\
M
aj3◦k (Z) ≤
n
Z∈span(S)

Proof. The Fourier expansion of M aj3 is given as M aj3 (x1 , x2 , x3 ) = 12 (x1 + x2 + x3 − x1 x2 x3 ).
For i ∈ {1, 2, 3} let Ni = {(i − 1)n/3 + 1, . . . , in/3}. Let Si = S ∩ Ni . Let αi be defined as:
2
X  \
◦k−1
M aj3
(Z) .
αi =
Z∈span(Si )

Then we have:
X

Z∈span(S)

3

2 X
\
M
aj3◦k (Z) =

X

i=1 Z∈span(Si )


2
\
M
aj3◦k (Z) +

X

Z∈span(S)−∪3i=1 span(Si )


2
\
M
aj3◦k (Z) .

For each Si we have
X

Z∈span(Si )


2 1
\
M
aj3◦k (Z) =
4

X

Z∈span(Si )



2
αi
\
◦k−1
M aj3
(Z) = .
4

Moreover, for each Z ∈ span(S) − ∪3i=1 span(Si ) we have:
(
aj3◦k−1 (Z1 )M\
aj3◦k−1 (Z2 )M\
aj3◦k−1 (Z3 )
− 12 M\
\
◦k
M aj3 (Z) =
0
13

if Z ∈ ×3i=1 (span(Si ) \ ∅)
otherwise.

Thus, we have:
X

Z∈(span(S1 )\∅)×(span(S2 )\∅)×(span(S3 )\∅)

=

X


2
\
M
aj3◦k (Z)

Z∈(span(S1 )\∅)×(span(S2 )\∅)×(span(S3 )\∅)

1
=
4
=

X

Z∈(span(S1 )\∅)



2
\
◦k−1
M aj3
(Z1 )

1
4



2
2 
2 
\
\
\
◦k−1
◦k−1
◦k−1
M aj3
(Z3 )
M aj3
(Z2 )
M aj3
(Z1 )

X

Z∈(span(S2 )\∅)

1
α1 α2 α3 .
4



2
\
◦k−1
M aj3
(Z2 )

X

Z∈(span(S3 )\∅)



2
\
◦k−1
M aj3
(Z3 )

where the last equality holds since M\
aj3◦k−1 (∅) = 0. Putting this together we have:

2 1
\
M
aj3◦k (Z) = (α1 + α2 + α3 + α1 α2 α3 )
4
Z∈span(S)


1
1
1
α1 + α2 + α3 + (α1 + α2 + α3 ) = (α1 + α2 + α3 ).
≤
4
3
3
X

Applying this argument recursively to each αi for k − 1 times we have:
X

Z∈span(S)

3k

2
1 X
\
◦k
M aj3 (Z) ≤ k
γi ,
3

where γi = 1 if i ∈ S and 0 otherwise. Thus,

i=1

P


2
\
◦k (Z)
M
aj
≤
3
Z∈span(S)

|S|
n .

To extend the argument to arbitrary linear subspaces we show that any such subspace has less
Fourier weight than a collection of three carefully chosen standard subspaces. First we show how
to construct such subspaces in Lemma 4.4.
For a linear subspace L ≤ Fn2 we denote the set of all vectors in L of odd Hamming weight as
O(L) and refer to it as the odd set of L. For two vectors v1 , v2 ∈ Fn2 we say that v1 dominates v2 if the
set of non-zero coordinates of v1 is a (not necessarily proper) subset of the set of non-zero coordinates
of v2 . For two sets of vectors S1 , S2 ⊆ Fn2 we say that S1 dominates S2 (denoted as S1 ≺ S2 ) if
there is a matching M between S1 and S2 of size |S2 | such that for each (v1 ∈ S1 , v2 ∈ S2 ) ∈ M
the vector v1 dominates v2 .
Lemma 4.4 (Standard subspace domination lemma). For any linear subspace L ≤ Fn2 of dimension
d there exist three standard linear subspaces S1 , S2 , S3 ≤ Fn2 such that:
O(L) ≺ O(S1 ) ∪ O(S2 ) ∪ O(S3 ),
and dim(S1 ) = d − 1, dim(S2 ) = d, dim(S3 ) = 2d.
Proof. Let A ∈ Fd×n
be the matrix with rows corresponding to the basis in L. We will assume that
2
A is normalized in a way described below. First, we apply Gaussian elimination to ensure that
14

A = (I, M ) where I is a d × d identity matrix. If all rows of A have even Hamming weight then the
lemma holds trivially since O(L) = ∅. By reordering rows and columns of A we can always assume
that for some k ≥ 1 the first k rows of A have odd Hamming weight and the last d − k have even
Hamming weight. Finally, we add the first column to each of the last d − k rows, which makes all
rows have odd Hamming weight. This results in A of the following form:


0···0
a
1 0···0

 0

 .
 ..


k−1
1


A= 0


 1

 .

 .
.
d−k
2
1

0

I

0

I

M
M

We use the following notation for submatrices: A[i1 , j1 ; i2 , j2 ] refers to the submatrix of A with
rows between i1 and j1 and columns between i2 and j2 inclusive. We denote to the first row as v,
the submatrix A[2,
P k; 1, n] as A and the submatrix A[k + 1, d; 1, n] as B. Each x ∈ O(L) can be
represented as i∈S Ai where the set S is of odd size and the sum is over Fn2 . We consider the
following three cases corresponding to different types of the set S.
Case 1. S ⊆ rows(A) ∪ rows(B). This corresponds to all odd size linear combinations of
the rows of A that don’t include the first row. Clearly, the set of such vectors is dominated by
O(S1 ) where S1 is the standard subspace corresponding to the span of the rows of the submatrix
A[2, d; 2, d].
Case 2. S contains the first row, |S ∩ rows(A)| and |S ∩ rows(B)| are even. All such linear
combinations have their first coordinate equal 1. Hence, they are dominated by a standard subspace
corresponding to span of the rows the d × d identity matrix, which we refer to as S2 .
Case 3. S contains the first row, |S ∩ rows(A)| and |S ∩ rows(B)| are odd. All such linear
combinations have their first coordinate equal 0. This implies that the Hamming weight of the first
d coordinates of such linear combinations is even and hence the other coordinates can’t be all equal
to 0. Consider the submatrix M = A[1, d; d + 1, n] corresponding to the last n − d columns of A.
Since the rank of this matrix is at most d by running Gaussian elimination on M we can construct
a matrix M ′ containing as rows the basis for the row space of M of the following form:


It M1
′
M =
0
0
where t = rank(M ). This implies that any non-trivial linear combination of the rows of M contains
1 in one of the first t coordinates. We can reorder the columns of A in such a way that these t
coordinates have indices from d+ 1 to d+ t. Note that now the set of vectors spanned by the rows of
the (d+t)×(d+t) identity matrix Id+t dominates the set of linear combinations we are interested in.
Indeed, each such linear combination has even Hamming weight in the first d coordinates and has
at least one coordinate equal to 1 in the set {d + 1, . . . , d + t}. This gives a vector of odd Hamming
weight that dominates such linear combination. Since this mapping is injective we have a matching.
We denote the standard linear subspace constructed this way as S3 and clearly dim(S3 ) ≤ 2d.
The following proposition shows that the spectrum of the M aj3◦k is monotone decreasing under
inclusion if restricted to odd size sets only:
15

Proposition 4.5. For any two sets Z1 ⊆ Z2 of odd size it holds that:
\
\
M
aj3◦k (Z1 ) ≥ M
aj3◦k (Z2 ) .
Proof. The proof is by induction on k. Consider the Fourier expansion of M aj3 (x1 , x2 , x3 ) =
1
2 (x1 + x2 + x3 − x1 x2 x3 ). The case k = 1 holds since all Fourier coefficients have absolute value
1/2. Since M aj3◦k = M aj3 ◦ (M aj3◦k−1 ) all Fourier coefficients of M aj3◦k result from substituting
either a linear or a cubic term in the Fourier expansion by the multilinear expansions of M aj3◦k−1 .
This leads to four cases.
Case 1. Z1 and Z2 both arise from linear terms. In this case if Z1 and Z2 aren’t disjoint then
they arise from the same linear term and thus satisfy the statement by the inductive hypothesis.
Case 2. If Z1 arises from a cubic term and Z2 from the linear term then it can’t be the case
that Z1 ⊆ Z2 since Z2 contains some variables not present in Z1 .
Case 3. If Z1 and Z2 both arise from the cubic term then we have (Z1 ∩ Ni ) ⊆ (Z2 ∩ Ni )
for each i. By the inductive hypothesis we then have M\
aj ◦k−1 (Z ∩ N ) ≥ M\
aj ◦k−1 (Z ∩ N ) .
3

1

i

3

2

i

Q
\
aj3◦k−1 (Zj ∩ Ni ) the desired inequality follows.
Since for j = 1, 2 we have M
aj3◦k (Zj ) = − 21 i M\
Case 4. If Z1 arises from the linear term and Z2 from the cubic term then w.l.o.g. assume that
Z1 arises from the x1 term. Note that Z1 ⊆ (Z2 ∩ N1 ) since Z1 ∩ (N2 ∪ N3 ) = ∅. By the inductive
hypothesis applied to Z1 and Z2 ∩ N1 the desired inequality holds.
We can now complete the proof of Theorem 4.2

Proof of Theorem 4.2. By combining Proposition 4.5 and Lemma 4.3 we have that any set T of vecP
\
tors that is dominated by O(S) for some standard subspace S satisfies S∈T M
aj3◦k (S)2 ≤ dim(S)
.
n
n
By the standard subspace domination lemma (Lemma 4.4) any subspace L ≤ F2 of dimension d has
O(L) dominated by a union of three standard subspaces of dimension 2d, d and d − 1 respectively.
P
\
Thus, we have
M
aj ◦k (S)2 ≤ 2d + d + d−1 ≤ 4d .
S∈O(L)

3

n

n

n

n

We have the following corollary of Theorem 4.2 that proves Theorem 1.5.

Corollary 4.6. For any ǫ ∈ [0, 1], γ <

1
2

− ǫ and k = log3 n it holds that:
+

(M aj3◦k ) ≥ ǫ2 n + 1.
D →,U
1 1
2)
−ǫ
(
n 4

Dγlin,U (M aj3◦k ) ≥ ǫ2 n + 1,

Proof. Fix d = ǫ2 n. For this choice of d Theorem 4.2 implies that ǫd (M aj3◦k ) ≤ 4ǫ2 . The firstppart
follows from Part 2 of Theorem 3.4. The second part is by Corollary 3.11 as by taking ǫ = d/n
we can set θ = 4ǫ2 ≥ ǫd (M aj3◦k ) and hence:
→,U
→,U
◦k
◦k
ǫ2 n + 1 ≤ D →,U
(M aj3◦k ).
1−θ (M aj3 ) = D 1−4ǫ2 (M aj3 ) ≤ D 1 1
2
−ǫ
(
)
4(n−d)
n
4
4n(1−ǫ2 )

16

4.2

Address function and Fourier sparsity

Consider the addressing function Addn : {0, 1}log n+n → {0, 1}8 defined as follows:
Addn (x, y1 , . . . , yn ) = yx , where x ∈ {0, 1}log n , yi ∈ {0, 1},
i.e. the value of Addn on an input (x, y) is given by the x-th bit of the vector y where x is treated
as a binary representation of an integer number in between 1 and n. Addressing function has only
n2 non-zero Fourier coefficients. In fact, as shown by Sanyal [San15] Fourier dimension, and hence
by Fact A.1 also the deterministic sketch complexity, of any Boolean function with Fourier sparsity
√
s is O( s log s).
Below using the addressing function we show that this relationship is tight (up to a logarithmic
factor) even if randomization is allowed, i.e. even for a function with Fourier sparsity s an F2 sketch
√
of size Ω( s) might be required.
Theorem 4.7. For the addressing function Addn and values 1 ≤ d ≤ n and ǫ = d/n it holds that:
→,U
DΘ(
1−ǫ (Addn ) ≥ d.
)

+
√
D lin,U
1− ǫ (Addn ) ≥ d,

n

2

Proof. If we apply the standard Fourier notaion switch where we replace 0 with 1 and 1 with −1 in
the domain and the range of the function then the addressing function Addn (x, y) can be expressed
as the following multilinear polynomial:
X
Y  1 − xj  Y  1 + xj 
,
Addn (x, y) =
yi
2
2
log n
i∈{0,1}

j : ij =1

j : ij =0

which makes it clear that the only non-zero Fourier coefficents correspond to the sets that contain
a single variable from the addressee block and an arbitrary subset of variables from the address
block. This expansion also shows that the absolute value of each Fourier coefficient is equal to n1 .
d×(log n+n)

Fix any d-dimensional subspace Ad and consider the matrix M ∈ F2
composed of the
basis vectors as rows. We add to M extra log n rows which contain an identity matrix in the first
(d+log n)×(log n+n)
log n coordinates and zeros everywhere else. This gives us a new matrix M ′ ∈ F2
.
′
Applying Gaussian elimination to M we can assume that it is of the following form:


Ilog n 0
0
Id′ M  ,
M′ =  0
0
0
0

where d′ ≤ d. Thus, the total number of non-zero Fourier coefficients spanned by the rows of
′
M ′ equals nd′ . Hence, the total sum of squared Fourier coeffients in Ad is at most dn ≤ nd , i.e.
ǫd (Addn ) ≤ nd . By Part 2 of Theorem 3.4 and Corollary 3.11 the statement of the theorem follows.

8
In this section it will be more convenient to represent both domain and range of the function using {0, 1} rather
than F2 .

17

4.3

Symmetric functions

A function f : Fn2 → F2 is symmetric if it can be expressed as g(kxk0 ) for some function g : [0, n] →
F2 . We give the following lower bound for symmetric functions:
Theorem 4.8 (Lower bound for symmetric functions). For any symmetric function f : Fn2 → F2
that isn’t (1 − ǫ)-concentrated on {∅, {1, . . . , n}}:
lin,U
(f ) ≥
Dǫ/8

n
,
2e

→,U
+
DΘ(
1−ǫ (f ) ≥
)
n

n
.
2e

Proof. First we prove an auxiliary lemma. Let Wk be the set of all vectors in Fn2 of Hamming
weight k.
Lemma 4.9. For any d ∈ [n/2], k ∈ [n − 1] and any d-dimensional subspace Ad ≤ Fn2 :
 min(k,n−k,d)
ed
ed
|Wk ∩ Ad |
≤ .
≤
|Wk |
n
n
Proof. Fix any basis in Ad and consider the matrix M ∈ Fd×n
composed of the basis vectors as
2
rows. W.l.o.g we can assume that this matrix is diagonalized and is in the standard form (Id , M ′ )
where Id is a d × d identity matrix and M ′ is a d × (n − d)-matrix. Clearly, any linear combination
of more than k rows of M has Hamming weightPgreater than k just from the contribution of the
first d coordinates. Thus, we have |Wk ∩ Ad | ≤ ki=0 di .
k

P
. On the other hand,
For any k ≤ d it is a standard fact about binomials that ki=0 di ≤ ed
k

|Wk ∩Ad |
n
ed k
k
we have |Wk | = k ≥ (n/k) . Thus, we have |Wk | ≤ n
and hence for 1 ≤ k ≤ d the desired
inequality holds.
If d < k then consider two cases. Since d ≤ n/2 the case n − d ≤ k ≤ n − 1 is symmetric to
1 ≤ k ≤ d. If d < k < n − d then we have |Wk | > |Wd | ≥ (n/d)d and |Wk ∩ Ad | ≤ 2d so that the
desired inequality follows.
Any symmetric function
P has its spectrum distributed uniformly over Fourier coefficients
Pn−1 of any
fixed weight. Let wi = S∈Wi fˆ2 (S). By the assumption of the theorem we have i=1
wi ≥ ǫ.
Thus, by Lemma 4.9 any linear subspace Ad of dimension at most d ≤ n/2 satisfies that:
X

S∈Ad

f (S) ≤ fˆ2 (∅) + fˆ2 ({1, . . . , n}) +
2

≤ fˆ2 (∅) + fˆ2 ({1, . . . , n}) +
ed
≤ (1 − ǫ) + ǫ .
n

n−1
X

wi

|Wi ∩ Ad |
|Wi |

wi

ed
n

i=1

n−1
X
i=1

Thus, f isn’t 1 − ǫ(1 − ed
n )-concentrated on any d-dimensional linear subspace, i.e. ǫd (f ) <
ed
1 − ǫ(1 − n ). By Part 2 of Theorem 3.4 this implies that f doesn’t have randomized sketches of
dimension at most d which err with probability less than:
q


1 − ǫ(1 − ed
1
ǫ
ed
ǫ
n)
−
≥
1−
≥
2
2
4
n
8
18

where the last inequality follows by the assumption that d ≤
lower bound follows by Corollary 3.11 by taking θ = ǫ/8.

5

n
2e .

The communication complexity

Turnstile streaming algorithms over F2

Let ei be the standard unit vector in Fn2 . In the turnstile streaming model the input x ∈ Fn2 is
represented as a stream σ = (σ1 , σ2 , . . . ) where σi ∈ P
{e1 , . . . , en }. For a stream σ the resulting
vector x corresponds to its frequency vector freq σ ≡ i σi . Concatenation of two streams σ and
τ is denoted as σ ◦ τ .

5.1

Random streams

We consider the following two natural models of random streams over F2 :
Model 1. In the first model we start with x ∈ Fn2 that is drawn from the uniform distribution
over Fn2 and then apply a uniformly random update y ∼ U (Fn2 ) obtaining x + y. In the streaming
language this corresponds to a stream σ = σ1 ◦ σ2 where freq σ1 ∼ U (Fn2 ) and freq σ2 ∼ U (Fn2 ). A
specific example of such stream would be one where for both σ1 and σ2 we flip an unbiased coin to
decide whether or not to include a vector ei in the stream for each value of i. The expected length
of the stream in this case is n.
Model 2. In the second model we consider a stream σ which consists of uniformly random
updates. Let σi = er(i) where r(i) ∼ U ([n]). This corresponds to each update being a flip in a
coordinate of x chosen uniformly at random. This model is equivalent to the previous model but
requires longer streams to mix. Using coupon collector’s argument such streams of length Θ(n log n)
can be divided into two substreams σ1 and σ2 such that with high probability both freq σ1 and
freq σ2 are uniformly distributed over Fn2 and σ = σ1 ◦ σ2 .
Theorem 5.1. Let f : Fn2 → F2 be an arbitrary function. In the two random streaming models
for generating σ described above any algorithm that computes f (freq σ) with probability at least
lin,U
(f ).
1 − Θ(1/n) in the end of the stream has to use space that is at least D1/3
Proof. The proof follows directly from Theorem 1.4 as in both models we can partition the stream
into σ1 and σ2 such that freq σ1 and freq σ2 are both distributed uniformly over Fn2 . We treat these
two frequency vectors as inputs of Alice and Bob in the communication game. Since communication
→,U
lin,U
DΘ(1/n)
(f + ) ≥ D1/3
(f ) is required no streaming algorithm with less space exists as otherwise Alice
would transfer its state to Bob with less communication.

5.2

Adversarial streams

We now show that any randomized turnstile streaming algorithm for computing f : Fn2 → F2 with
lin (f ) − O(log n + log(1/δ)) under adversarial
error probability δ has to use space that is at least R6δ
sequences of updates. The proof is based on the recent line of work that shows that this relationship holds for real-valued sketches [Gan08, LNW14, AHLW16]. The proof framework developed
by [Gan08, LNW14, AHLW16] for real-valued sketches consists of two steps. First, a turnstile
streaming algorithm is converted into a path-independent stream automaton (Definition 5.3). Second, using the theory of modules and their representations it is shown that such automata can
always be represented as linear sketches. We observe that the first step of this framework can be
19

left unchanged under F2 . However, as we show the second step can be significantly simplified as
path-independent automata over F2 can be directly seen as linear sketches without using module
theory. Furthermore, since we are working over F2 we also avoid the O(log m) factor loss in the
reduction between path independent automata and linear sketches that is present in [Gan08].
We use the following abstraction of a stream automaton from [Gan08, LNW14, AHLW16]
adapted to our context to represent general turnstile streaming algorithms over F2 .
Definition 5.2 (Deterministic Stream Automaton). A deterministic stream automaton A is a
Turing machine that uses two tapes, an undirectional read-only input tape and a bidirectional work
tape. The input tape contains the input stream σ. After processing the input, the automaton writes
an output, denoted as φA (σ), on the work tape. A configuration (or state) of A is determined by
the state of its finite control, head position, and contents of the work tape. The computation of
A can be described by a transition function ⊕A : C × F2 → C, where C is the set of all possible
configurations. For a configuration c ∈ C and a stream σ, we denote by c ⊕A σ the configuration of
A after processing σ starting from the initial configuration c. The set of all configurations of A that
are reachable via processing some input stream σ is denoted as C(A). The space of A is defined as
S(A) = log |C(A)|.
We say that a deterministic stream automaton computes a function f : Fn2 → F2 over a distribution Π if Prσ∼Π [φA (σ) = f (freq σ)] ≥ 1 − δ.
Definition 5.3 (Path-independent automaton). An automaton A is said to be path-independent
if for any configuration c and any input stream σ, c ⊕A σ depends only on freq σ and c.
Definition 5.4 (Randomized Stream Automaton). A randomized stream automaton A is a deterministic automaton with an additional tape for the random bits. This random tape is initialized
with a random bit string R before the automaton is executed. During the execution of the automaton
this bit string is used in a bidirectional read-only manner while the rest of the execution is the same
as in the deterministic case. A randomized automaton A is said to be path-independent if for each
possible fixing of its randomness R the deterministic automaton AR is path-independent. The space
complexity of A is defined as S(A) = maxR (|R| + S(AR )).
Theorems 5 and 9 of [LNW14] combined with the observation in Appendix A of [AHLW16] that
guarantees path independence yields the following:
Theorem 5.5 (Theorems 5 and 9 in [LNW14] + [AHLW16]). Suppose that a randomized stream
automaton A computes f on any stream with probability at least 1 − δ. For an arbitrary distribution
Π over streams there exists a deterministic9 path independent stream automaton B that computes
f with probability 1 − 6δ over Π such that S(B) ≤ S(A) + O(log n + log(1/δ)).
The rest of the argument below is based on the work of Ganguly [Gan08] adopted for our needs.
Since we are working over a finite field we also avoid the O(log m) factor loss in the reduction
between path independent automata and linear sketches that is present in Ganguly’s work.
Let An be a path-independent stream automaton over F2 and let ⊕ abbreviate ⊕An . Define
the function ∗ : Fn2 × C(An ) → C(An ) as: x ∗ a = a ⊕ σ, where f req(σ) = x. Let o be the initial
configuration of An . The kernel MAn of An is defined as MAn = {x ∈ Fn2 : x ∗ o = 0n ∗ o}.
9

We note that [LNW14] construct B as a randomized automaton in their Theorem 9 but it can always be made
deterministic by fixing the randomness that achieves the smallest error.

20

Proposition 5.6. The kernel MAn of a path-independent automaton An is a linear subspace of Fn2 .
Proof. For x, y ∈ MAn by path independence (x + y) ∗ o = x ∗ (y ∗ o) = 0n ∗ o so x + y ∈ MAn .
Since MAn ≤ Fn2 the kernel partitions Fn2 into cosets of the form x + MAn . Next we show that
there is a one to one mapping between these cosets and the states of An .
Proposition 5.7. For x, y ∈ Fn2 and a path independent automaton An with a kernel MAn it holds
that x ∗ o = y ∗ o if and only if x and y lie in the same coset of MAn .
Proof. By path independence x∗o = y ∗o iff x∗(x∗o) = x∗(y ∗o) or equivalently 0n ∗o = (x+ y)∗o.
The latter condition holds iff x + y ∈ MAn which is equivalent to x and y lying in the same cost of
MAn .
The same argument implies that the the transition function of a path-independent automaton
has to be linear since (x + y) ∗ o = x ∗ (y ∗ o). Combining these facts together we conclude that
a path-independent automaton has at least as many states as the best deterministic F2 -sketch for
f that succeeds with probability at least 1 − 6δ over Π (and hence the best randomized sketch as
well). Putting things together we get:
Theorem 5.8. Any randomized streaming algorithm that computes f : Fn2 → F2 under arbitrary
lin (f ) − O(log n +
updates over F2 with error probability at least 1 − δ has space complexity at least R6δ
log(1/δ)).

6

Linear threshold functions

In this section it will be convenient to represent the domain as {0, 1}n rather than Fn2 . We define
the sign function sign(x) to be 1 if x ≥ 0 and 0 otherwise.
Definition 6.1. A monotone linear threshold function (LTF) f : {0, 1} → {+1, −1} is defined by
a collection of weights w1 ≥ w2 · · · ≥ wn ≥ 0 as follows:
!
n
X
wi xi − θ ,
f (x1 , . . . , xn ) = sign
i=1

where θ is called the threshold of the LTF. The margin of the LTF is defined as:
m=

min

x∈{0,1}n

n
X
i=1

wi xi − θ .

P
W.l.o.g we can assume that LTFs normalized so that ni=1 wi = 1. The monotonicity in the
above definition is also without loss of generality as for negative weights we can achieve monotonicity
by complementing individual bits.

θ 2
).
Theorem 6.2. [MO09] There is a randomized linear sketch for LTFs of size O( m
Below we prove the following conjecture.

Conjecture 6.3. [MO09] There is a randomized linear sketch for LTFs of size O
21

θ
m

log

θ
m



.

In fact, all weights which are below the margin can be completely ignored when evaluating the
LTF.
Lemma 6.4. Let f be a monotone LTF with weights w1 ≥ w2 ≥ · · · ≥ wn , threshold θ and
margin m. Let f ≥2m be an LTF with the same threshold and margin but only restricted to weights
w1 ≥ w2 ≥ · · · ≥ wt , where t is the largest integer such that wt ≥ 2m. Then f = f ≥m .
Proof. For the sake of contradiction assume there exists an input (x1 , . . ., xn ) such that f(x1 , . . . , xn ) =
Pt∗
1 while f ≥2m (x1 , . . . , xt ) = 0. Fix the largest t∗ ≥ t such that sign
i=1 wi xi − θ = 0 while
P ∗

t +1
sign
i=1 wi xi − θ = 1. Clearly wt∗ +1 ≥ 2m, a contradiction.
The above lemma implies that after dropping the weights which are below 2m together with
the corresponding variables and reducing the value of n accordingly we can also make the margin
equal to wn /2. This observation also gives the following straightforward corollary that proves
Conjecture 6.3 about LTFs (up to a logarithmic factor in n).

θ
log n .
Corollary 6.5. There is a randomized linear sketch for LTFs of size O m
P
Proof. We will give a bound on |{x : f (x) = 0}|. If f (x) = 0 then  ni=1 wi xi < θ. Since all weights
n
n
= θ/2m
≤ (n + 1)θ/2m . Thus
are at least wn the total number of such inputs is at most θ/w
n

θ
log n as desired.
applying the random F2 -sketching bound (Fact B.7) we get a sketch of size O m
Combined with Theorem 6.2 the above corollary proves Conjecture 6.3 except in the case when
β log (θ/m) < θ/m < nα for all α > 0 and β < ∞. This matches the result of [LZ13].
A full proof of Conjecture 6.3 can be obtained by using hashing to reduce the size of the domain
from n down to poly(θ/m).

θ
θ
Theorem 6.6. There is a randomized linear sketch for LTFs of size O m
log m
that succeeds
with any constant probability.
Proof. It suffices to only consider the case when θ/m > 100 since P
otherwise the bound follows
trivially from Theorem 6.2. Consider computing a single linear sketch i∈S xi where S is a random
vector in Fn2 with each coordinate set to 1 independently with probability 10m2 /θ 2 . This sketch
lets us distinguish the two cases kxk0 > θ 2 /m2 vs. kxk0 ≤ θ/m with constant probability. Indeed:
Case 1. kxk0 > θ 2 /m2 . The probability that a set S contains a non-zero coordinate of x in
this case is at least:
 θ2

10m2 m2
≥ 1 − (1/e)10 > 0.9
1− 1−
θ2
Conditioned on this event the parity evaluate to 1 with probability at least 1/2. Hence, overall in
this case the parity evaluates to 1 with probability at least 0.4.
Case 2. kxk0 ≤ θ/m. In this case this probability that S contains a non-zero coordinate and
hence the parity can evaluate to 1 is at most:


10m2
1− 1−
θ2

θ/m

< 1 − (1/2e)1/10 < 0.2

22

Thus, a constant number of such sketches allows to distinguish the two cases above with constant
probability. If the test above declares that kxk0 > θ 2 /m2 then we output 1 and terminate. Note that
conditioned on the test above being correct it never declares that kxk0 > θ 2 /m2 while kxk0 ≤ θ/m.
Indeed in all such cases, i.e. when kxk0 > θ/m we can output 1 since if kxk0 > θ/m then
P
n
θwn
i=1 wi xi ≥ kxk0 wn ≥ m = 2θ, where we used the fact that by Lemma 6.4 we can set m = wn /2.
For the rest of the proof we thus condition on the event that kxk0 ≤ θ 2 /m2 . By hashing the
domain [n] randomly into O θ 4 /m4 buckets we can ensure that no non-zero entries of x collide
with any constant probability that is arbitrarily close to 1. This reduces the input length from n
down to O θ 4 /m4 and we can apply Corollary 6.5 to complete the proof. 10

This result is also tight as follows from the result of Dasgupta, Kumar and Sivakumar [DKS12]
discussed in the introduction. Consider the Hamming weight function Ham≥d (x) ≡ kxk0 ≥ d. This
function satisfies θ = d/n, m = 1/2n. A straightforward reduction from small set disjointness shows
that the one-way communication complexity of the XOR-function Ham≥d (x⊕ y) is Ω(d log d). This
shows that the bound in Theorem 6.6 can’t be improved without any further assumptions about
the LTF.

7

Towards the proof of Conjecture 1.3

We call a function f : Fn2 → {+1, −1} non-linear if for all S ∈ Fn2 there exists x ∈ Fn2 such that
f (x) 6= χS (x). Furthermore, we say that f is ǫ-far from being linear if:


maxn
Pr n [χS (x) = f (x)] = 1 − ǫ.
S∈F 2

x∼U (F 2 )

The following theorem is our first step towards resolving Conjecture 1.3. Since non-linear
functions don’t admit 1-bit linear sketches we show that the same is also true for the corresponding
communication complexity problem, namely no 1-bit communication protocol for such functions
can succeed with a small constant error probability.
→
Theorem 7.1. For any non-linear function f that is at most 1/10-far from linear D1/200
(f + ) > 1.


Proof. Let S = arg maxT Prx∈F n2 [χT (x) = f (x) . Pick z ∈ Fn2 such that f (z) 6= χS (z). Let the
distribution over the inputs (x, y) be as follows: y ∼ U (Fn2 ) and x ∼ Dy where Dy is defined as:
(
y + z with probability 1/2,
Dy =
U (Fn2 ) with probability 1/2.

Fix any deterministic Boolean function M (x) that is used by Alice to send a one-bit message based
on her input. For a fixed Bob’s input y he outputs gy (M (x)) for some function gy that can depend
on y. Thus, the error that Bob makes at predicting f for fixed y is at least:
1−

[gy (M (x))f (x + y)]
.
2
The key observation is that since Bob only receives a single bit message there are only four possible
functions gy to consider for each y: constants −1/1 and ±M (x).
x∼Dy

10
We note that random hashing doesn’t interfere with the linearity of the sketch as it corresponds to treating
collections of variables that have the same hash as a single variable representing their sum over F2 . Assuming no
collisions this sum evaluates to 1 if and only if a variable of interest is present in the collection.

23

Bounding error for constant estimators.
Byc = x∼Dy [gy (M (x))f (x + y)] and have:
Byc =

x∼Dy

[gy (M (x))f (x + y)] = |

If χS is not constant then
1
1
f (z) +
2
2

x∼Dy [f (x

[f (w)]
w∼U (F n
2)

w∼U (F n
2)

[f (w)] ≤

For both constant functions we introduce notation

+ y)]| =

1
1
f (z) +
2
2

≤ 2ǫ we have:

1
|f (z)| +
2

w∼U (F n
2)

If χS is a constant then w.l.o.g χS = 1 and f (z) = −1. Also
we have:
1
1
f (z) +
2
2

[f (w)]
w∼U (F n
2)

Since ǫ ≤ 1/10 in both cases Byc ≤

1
2

[f (w)]
w∼U (F n
2)

=

1
−1 +
2

[f (w)]



≤ 1/2 + ǫ.

[f (w)]
w∼U (F n
2)

[f (w)]
w∼U (F n
2)

≥ 1 − 2ǫ. Hence

≤ ǫ.

+ ǫ which is the bound we will use below.

Bounding error for message-based estimators. For functions ±M (x) we need to bound
M
M
x∼Dy [M (x)f (x + y)] . We denote this expression as By . Proposition 7.2 shows that y [By ] ≤
√

2
2

(1 + ǫ).

Proposition 7.2.
We have:

y

=

x∼Dy

y



y∼U (F n
2)



x∼Dy

[M (x)f (x + y)]

1
M (y + z)f (z) +
2



[M (x)f (x + y)]



≤


x∼Dy [M (x)f (x + y)]

√

2
2

(1 + ǫ).



1
y [|(M (y + z)f (z) + (M ∗ f )(y))|]
2
i1/2
1 h
2
≤
y ((M (y + z)f (z) + (M ∗ f )(y)))
2

1/2
1
=
(M (y + z)f (z))2 + ((M ∗ f )(y))2 + 2M (y + z)f (z)(M ∗ f )(y))
y
2


1/2


1
(M (y + z)f (z))2 + y ((M ∗ f )(y))2 + 2 y [M (y + z)f (z)(M ∗ f )(y)))
=
y
2
=

We have (M (y + z)f (z))2 = 1 and also by Parseval, expression for the Fourier spectrum of
convolution and Cauchy-Schwarz:
X
X
2
c(S)2 fˆ(S)2 ≤ ||M ||2 ||f ||2 = 1
\
M
M
∗ f (S)2 =
y [((M ∗ f )(y)) ] =
S∈F n
2

S∈F n
2

24

[M (y + z)f (z)(M ∗ f )(y))]. First we give a bound on

Thus, it suffices to give a bound on
(M ∗ f )(y):
(M ∗ f )(y) =

x [M (x)f (x

+ y)] ≤

x [M (x)χS (x

+ y)] + 2ǫ

Plugging this in we have:
y [M (y

+ z)f (z)(M ∗ f )(y))]

= −χS (z)

≤ −χS (z)

y [M (y
y

+ z)(M ∗ f )(y))]

[M (y + z)(M ∗ χS )(y)] + 2ǫ

= −χS (z)(M ∗ (M ∗ χS ))(z) + 2ǫ

= −χS (z)2 M̂ (S)2 + 2ǫ

≤ 2ǫ.

where we used the fact that the Fourier spectrum of (M ∗ (M ∗ χS )) is supported on S only and
M ∗\
(M ∗ χS )(S) = M̂ 2 (S) and thus (M ∗ (M ∗ χS ))(z) = M̂ 2 (S)χS (z).
Thus, overall, we have:
√

 1√
2
2 + 4ǫ ≤
(1 + ǫ).
x∼Dy [M (x)f (x + y)] ≤
y
2
2
Putting things together. We have that the error that Bob makes is at least:
#
"
1 − y [max(Byc , ByM )]
1 − max(Byc , ByM )
=
y
2
2
Below we now bound
1/200.

c
M
y [max(By , By )]

from above by 99/100 which shows that the error is at least

c
M
y [max(By , By )]



1
= Pr[ByM ≥ 1/2 + ǫ] [ByM |ByM ≥ 1/2 + ǫ] + P r[ByM < 1/2 + ǫ]
+ǫ
2


1
+ ǫ − [ByM |ByM < 1/2 + ǫ]
= y [ByM ] + P r[ByM < 1/2 + ǫ]
2
Let δ = P r[ByM < 1/2 + ǫ]. Then the first of the expressions above gives the following bound:


1
δ
δ
c
M
+ ǫ = 1 − + ǫδ ≤ 1 − + ǫ
y [max(By , By )] ≤ (1 − δ) + δ
2
2
2
The second expression gives the following bound:
√
√

 √
1
2
2 δ
2
c
M
(1 + ǫ) + δ
+ǫ ≤
+ +
ǫ + ǫ.
y [max(By , By )] ≤
2
2
2
2
2
√

2
These two bounds areequal for
 δ = 1 − 2 (1 + ǫ) and hence the best of the two bounds is always
√
√
99
1
at most ( 42 + 12 ) + ǫ 42 + 1 ≤ 100
where the last inequality uses the fact that ǫ ≤ 10
.

25

References
[AHLW16] Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. New Characterizations in Turnstile
Streams with Applications. In Ran Raz, editor, 31st Conference on Computational
Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:22, Dagstuhl, Germany, 2016. Schloss Dagstuhl–LeibnizZentrum fuer Informatik.
[AKLY16] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1345–1364, 2016.
[AMS99]

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating
the frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999.

[BTW15]

Eric Blais, Li-Yang Tan, and Andrew Wan. An inequality for the fourier spectrum of
parity decision trees. CoRR, abs/1506.01055, 2015.

[DKS12]

Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques - 15th International Workshop, APPROX
2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 517–528, 2012.

[Gan08]

Sumit Ganguly. Lower bounds on frequency estimation of data streams (extended abstract). In Computer Science - Theory and Applications, Third International Computer
Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, pages 204–215, 2008.

[GKdW04] Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf. Quantum communication cannot
simulate a public coin. CoRR, quant-ph/0411051, 2004.
[GOS+ 11] Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075–1100,
2011.
[Gro97]

Vince Grolmusz. On the power of circuits with gates of low l1 norms. Theor. Comput.
Sci., 188(1-2):117–128, 1997.

[HHL16]

Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR
functions. Electronic Colloquium on Computational Complexity (ECCC), 23:44, 2016.

[HPP+ 15] James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph
connectivity and MST. In Proceedings of the 2015 ACM Symposium on Principles
of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23,
2015, pages 91–100, 2015.

26

[HSZZ06]

Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the hamming distance problem. Inf. Process. Lett., 99(4):149–153, 2006.

[JKS03]

T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, USA, pages 673–682, 2003.

[KM93]

Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993.

[KN97]

Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University
Press, 1997.

[Leo13]

Nikos Leonardos. An improved lower bound for the randomized decision tree complexity
of recursive majority,. In Automata, Languages, and Programming - 40th International
Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages
696–708, 2013.

[LLZ11]

Ming Lam Leung, Yang Li, and Shengyu Zhang. Tight bounds on the randomized
communication complexity of symmetric XOR functions in one-way and SMP models.
CoRR, abs/1101.4555, 2011.

[LNW14]

Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might
as well be linear sketches. In Symposium on Theory of Computing, STOC 2014, New
York, NY, USA, May 31 - June 03, 2014, pages 174–183, 2014.

[Lov14]

Shachar Lovett. Recent advances on the log-rank conjecture in communication complexity. Bulletin of the EATCS, 112, 2014.

[LZ10]

Troy Lee and Shengyu Zhang. Composition theorems in communication complexity. In
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010,
Bordeaux, France, July 6-10, 2010, Proceedings, Part I, pages 475–489, 2010.

[LZ13]

Yang Liu and Shengyu Zhang. Quantum and randomized communication complexity of
XOR functions in the SMP model. Electronic Colloquium on Computational Complexity
(ECCC), 20:10, 2013.

[McG14]

Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9–20,
2014.

[MNS+ 13] Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, and
David Xiao. Improved bounds for the randomized decision tree complexity of recursive
majority. CoRR, abs/1309.7565, 2013.
[MNSX11] Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao. Improved bounds for
the randomized decision tree complexity of recursive majority. In Automata, Languages
and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland,
July 4-8, 2011, Proceedings, Part I, pages 317–329, 2011.
[MO09]

Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR
functions. CoRR, abs/0909.3392, 2009.
27

[O’D14]

Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

[OWZ+ 14] Ryan O’Donnell, John Wright, Yu Zhao, Xiaorui Sun, and Li-Yang Tan. A composition
theorem for parity kill number. In IEEE 29th Conference on Computational Complexity,
CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 144–154, 2014.
[San15]

Swagato Sanyal. Near-optimal upper bound on fourier dimension of boolean functions
in terms of fourier sparsity. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part
I, pages 1035–1045, 2015.

[STlV14]

Amir Shpilka, Avishay Tal, and Ben lee Volk. On the structure of boolean functions
with small spectral norm. In Innovations in Theoretical Computer Science, ITCS’14,
Princeton, NJ, USA, January 12-14, 2014, pages 37–48, 2014.

[SW86]

Michael E. Saks and Avi Wigderson. Probabilistic boolean decision trees and the complexity of evaluating game trees. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 29–38, 1986.

[SW12]

Xiaoming Sun and Chengu Wang. Randomized communication complexity for linear
algebra problems over finite fields. In 29th International Symposium on Theoretical
Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris,
France, pages 477–488, 2012.

[SZ08]

Yaoyun Shi and Zhiqiang Zhang. Communication complexities of symmetric xor functions. Quantum Inf. Comput, pages 0808–1762, 2008.

[TWXZ13] Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity,
spectral norm, and the log-rank conjecture. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA,
pages 658–667, 2013.
[Woo14]

David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and
Trends in Theoretical Computer Science, 10(1-2):1–157, 2014.

[Yao83]

Andrew Chi-Chih Yao. Lower bounds by probabilistic arguments (extended abstract).
In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona,
USA, 7-9 November 1983, pages 420–428, 1983.

[ZS10]

Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of boolean functions. Theor. Comput. Sci., 411(26-28):2612–2618, 2010.

28

Appendix
A

Deterministic F2-sketching

In the deterministic case it will be convenient to represent F2 -sketch of a function f : Fn2 → F2
as a d × n matrix Mf ∈ Fd×n
that we call the sketch matrix. The d rows of Mf correspond to
2
vectors α1 , . . . , αd used in the deterministic sketch so that the sketch can be computed as Mf x.
W.l.o.g below we will assume that the sketch matrix Mf has linearly independent rows and that
the number of rows in it is the smallest possible among all sketch matrices (ties in the choice of the
sketch matrix are broken arbitrarily).
The following fact is standard (see e.g. [MO09, GOS+ 11]):
Fact A.1. For any function f : Fn2 → F2 it holds that D lin (f ) = dim(f ) = rank(Mf ). Moreover,
set of rows of Mf forms a basis for a subspace A ≤ Fn2 containing all non-zero coefficients of f .

A.1

Disperser argument

We show that the following basic relationship holds between deterministic linear sketching complexity and the property of being an affine disperser. For randomized F2 -sketching an analogous
statement holds for affine extractors as shown in Lemma B.2.
Definition A.2 (Affine disperser). A function f is an affine disperser of dimension at least d if
for any affine subspace of Fn2 of dimension at least d the restriction of f on it is a non-constant
function.
Lemma A.3. Any function f : Fn2 → F2 which is an affine disperser of dimension at least d has
deterministic linear sketching complexity at least n − d + 1.
Proof. Assume for the sake of contradiction that there exists a linear sketch matrix Mf with
k ≤ n − d rows and a deterministic function g such that g(Mf x) = f (x) for every x ∈ Fn2 . For
any vector b ∈ Fk2 , which is in the span of the columns of Mf , the set of vectors x which satisfy
Mf x = b forms an affine subspace of dimension at least n − k ≥ d. Since f is an affine disperser for
dimension at least d the restriction of f on this subspace is non-constant. However, the function
g(Mf x) = g(b) is constant on this subspace and thus there exists x such that g(Mf x) 6= f (x), a
contradiction.

A.2

Composition and convolution

In order to prove a composition theorem for D lin we introduce the following operation on matrices
which for a lack of a better term we call matrix super-slam11 .
Definition A.4 (Matrix super-slam). For two matrices A ∈ Fa×n
and B ∈ Fb×m
their super-slam
2
2
n
abn ×nm
A†B ∈ F2
is a block matrix consisting of a blocks (A†B)i . The i-th block (A†B)i ∈ Fb2 ×nm is
constructed as follows: for every vector j ∈ {1, . . . , b}n the corresponding row of (A † B)i is defined
as (Ai,1 Bj1 , Ai,2 Bj2 , . . . , Ai,n Bjn ), where Bk denotes the kth row of B.
Proposition A.5. rank(A † B) ≥ rank(A)rank(B).
11

This name was suggested by Chris Ramsey.

29

Proof. Consider the matrix C which is a subset of rows of A † B where from each block (A † B)i we
select only b rows corresponding to the vectors j of the form αn for all α ∈ {1, . . . , b}. Note that
C ∈ Fab×mn
and C(i,k),(j,l) = Ai,j Bk,l . Hence, C is a Kronecker product of A and B and we have:
2
rank(A † B) ≥ rank(C) = rank(A)rank(B).
The following composition theorem for D lin holds as long as the inner function is balanced:
Lemma A.6. For f : Fn2 → F2 and g : Fm
2 → F2 if g is a balanced function then:
D lin (f ◦ g) ≥ D lin (f )D lin (g)

P
Proof. The multilinear expansions of f and g are given as f (y) = S∈F n fˆ(S)χS (y) and g(y) =
2
P
ĝ(S)χS (y). The multilinear expansion of f ◦g can be obtained as follows. For each monomial
S∈F m
2
fˆ(S)χS (y) in the multilinear expansion of f and each variable yi substitute yi by the multilinear

expansion of g on a set of variables xm(i−1)+1,...,mi . Multiplying all these multilinear expansions
corresponding to the term fˆ(S)χS gives a polynomial which is a sum of at most bn monomials
where b is the number of non-zero Fourier coefficients of g. Each such monomial is obtained by
picking one monomial from the multilinear expansions corresponding to different variables in χS and
multiplying them. Note that there are no cancellations between the monomials corresponding to a
fixed χS . Moreover, since g is balanced and thus ĝ(∅) = 0 all monomials corresponding to different
characters χS and χS ′ are unique since S and S ′ differ on some variable and substitution of g into
that variable doesn’t have a constant term but introduces new variables. Thus, the characteristic
vectors of non-zero Fourier coefficients of f ◦ g are the same as the set of rows of the super-slam of
the sketch matrices Mf and Mg (note, that in the super-slam some rows can be repeated multiple
times but after removing duplicates the set of rows of the super-slam and the set of characteristic
vectors of non-zero Fourier coefficients of f ◦ g are exactly the same). Using Proposition A.5 and
Fact A.1 we have:
D lin (f ◦ g) = rank(Mf ◦g ) = rank(Mf † Mg ) ≥ rank(Mf )rank(Mg ) = D lin (f )D lin (g).
Deterministic F2 -sketch complexity of convolution satisfies the following property:
Proposition A.7. D lin (f ∗ g) ≤ min(D lin (f ), D lin (g)).

Proof. The Fourier spectrum of convolution is given as f[
∗ g(S) = fˆ(S)ĝ(S). Hence, the set of
non-zero Fourier coefficients of f ∗ g is the intersection of the sets of non-zero coefficients of f and
g. Thus by Fact A.1 we have D lin (f ∗ g) ≤ min(rank(Mf , Mg )) = min(D lin (f ), D lin (g)).

B

Randomized F2-sketching

We represent randomized F2 -sketches as distributions over d × n matrices over F2 . For a fixed such
distribution Mf the randomized sketch is computed as Mf x. If the set of rows of Mf satisfies
Definition 1.1 for some reconstruction function g then we call it a randomized sketch matrix for f .

30

B.1

Extractor argument

We now establish a connection between randomized F2 -sketching and affine extractors which will
be used to show that the converse of Part 1 of Theorem 3.4 doesn’t hold for arbitrary distributions.
Definition B.1 (Affine extractor). A function f : Fn2 → F2 is an affine δ-extractor if for any affine
subspace A of Fn2 of dimension at least d it satisfies:
min

Pr [f (x) = z] > δ.

z∈{0,1} x∼U (A)

Lemma B.2. For any f : Fn2 → F2 which is an affine δ-extractor of dimension at least d it holds
that:
Rδlin (f ) ≥ n − d + 1.
Proof. For the sake of contradiction assume that there exists a randomized linear sketch with a
reconstruction function g : Fk2 → F2 and a randomized sketch matrix Mf which is a distribution
over matrices with k ≤ n − d rows. First, we show that:
Pr

x∼U (F n
2 )M ∼Mf

[g(M x) 6= f (x)] > δ.

Indeed, fix any matrix M ∈ supp(Mf ). For any affine subspace S of the form S = {x ∈ Fn2 |M x = b}
of dimension at least n − k ≥ d we have that minz∈{0,1} Prx∼U (S) [f (x) = z] > δ. This implies that
Prx∼U (S) [f (x) 6= g(M x)] > δ. Summing over all subspaces corresponding to the fixed M and all
possible choices of b we have that Prx∼U (F n2 ) [f (x) 6= g(M x)] > δ. Since this holds for any fixed M
the bound follows.
Using the above observation it follows by averaging over x ∈ {0, 1}n that there exists x∗ ∈ {0, 1}n
such that:
Pr

M ∼Mf

[g(M x∗ ) 6= f (x∗ )] > δ.

This contradicts the assumption that Mf and g form a randomized linear sketch of dimension
k ≤ n − d.
Pn/2
Fact B.3. The inner product function IP (x1 , . . . xn ) = i=1 x2i−1 ∧ x2i is an (1/2 − ǫ)-extractor
for affine subspaces of dimension ≥ (1/2 + α)n where ǫ = exp(−αn).
Corollary B.4. Randomized linear sketching complexity of the inner product function is at least
n/2 − O(1).
Remark B.5. We note that the extractor argument of Lemma B.2 is often much weaker than the
arguments we give in Part 2 and Part 3 Theorem 3.4 and wouldn’t suffice for our applications in
Section 4. In fact, the extractor argument is too weak even for the majority function M ajn . If the
√
first 100 n variables of M ajn are fixed to 0 then the resulting restriction has value 0 with probability
√
1 − e−Ω(n) . Hence for constant error M ajn isn’t an extractor for dimension greater than 100 n.
However, as shown in Section 4.3 for constant error F2 -sketch complexity of M ajn is linear.

31

B.2

Existential lower bound for arbitrary distributions

Now we are ready to show that an analog of Part 1 of Theorem 3.4 doesn’t hold for arbitrary
distributions, i.e. concentration on a low-dimensional linear subspace doesn’t imply existence of
randomized linear sketches of small dimension.
Lemma B.6. For any fixed constant ǫ > 0 there exists a function f : Fn2 → {+1, −1} such that
lin (f ) ≥ n − 3 log n such that f is (1 − 2ǫ)-concentrated on the 0-dimensional linear subspace.
Rǫ/8
Proof. The proof is based on probabilistic method. Consider a distribution over functions from Fn2
to {+1, −1} which independently assigns to each x value 1 with probability 1−ǫ/4 and value −1 with
n
probability ǫ/4. By a Chernoff bound with probability e−Ω(ǫ2 ) a random function
f drawn from
P
this distribution has at least an ǫ/2-fraction of −1 values and hence fˆ(∅) = 21n α∈F n f (x) ≥ 1 − ǫ.
2
This implies that fˆ(∅)2 ≥ (1 − ǫ)2 ≥ 1 − 2ǫ so f is (1 − 2ǫ)-concentrated on a linear subspace of

dimension 0. However, as we show below the randomized sketching complexity of some functions
in the support of this distribution is large.
The total number of affine subspaces of codimension d is at most (2 · 2n )d = 2(n+1)d since each
such subspace can be specified by d vectors in Fn2 and a vector in Fd2 . The number of vectors in each
such affine subspace is 2n−d . The probability that less than ǫ/8 fraction of inputs in a fixed subspace
n−d
have value −1 is by a Chernoff bound at most e−Ω(ǫ2 ) . By a union bound the probability that
a random function takes value −1 on less than ǫ/8 fraction of the inputs in any affine subspace of
n−d
codimension d is at most e−Ω(ǫ2 ) 2(n+1)d . For d ≤ n − 3 log n this probability is less than e−Ω(ǫn) .
By a union bound, the probability that a random function is either not an ǫ/8-extractor or isn’t
n
(1 − 2ǫ)-concentrated on fˆ(∅) is at most e−Ω(ǫn) + e−Ω(ǫ2 ) ≪ 1. Thus, there exists a function f
in the support of our distribution which is an ǫ/8-extractor for any affine subspace of dimension at
least 3 log n while at the same time is (1 − 2ǫ)-concentrated on a linear subspace of dimension 0.
By Lemma B.2 there is no randomized linear sketch of dimension less than n − 3 log n for f which
errs with probability less than ǫ/8.

B.3

Random F2 -sketching

The following result is folklore as it corresponds to multiple instances of the communication protocol
for the equality function [KN97, GKdW04] and can be found e.g. in [MO09] (Proposition 11). We
give a proof for completeness.
Fact B.7. A function f : Fn2 → F2 such that minz∈{0,1} Prx [f (x) = z] ≤ ǫ satisfies
Rδlin (f ) ≤ log

ǫ2n+1
.
δ

Proof. We assume that argminz∈{0,1} Prx [f (x) = z] = 1 as the other case is symmetric. Let
T = {x ∈ Fn2 |f (x) = 1}. For every two inputs x 6= x′ ∈ T a random F2 -sketch χα for α ∼ U (Fn2 )
satisfies Pr[χα (x) 6= χα (x′ )] = 1/2. If we draw t such sketches χα1 , . . . , χαt then Pr[χαi (x) =
χαi (x′ ), ∀i ∈ [t]] = 1/2t . For any fixed x ∈ T we have:
Pr[∃x′ 6= x ∈ T ∀i ∈ [t] : χαi (x) = χαi (x′ )] ≤

32

|T | − 1
ǫ2n
δ
≤
≤ .
t
t
2
2
2

Conditioned on the negation of the event above for a fixed x ∈ T the domain of f is partitioned by
the linear sketches into affine subspaces such that x is the only element of T in the subspace that
contains it. We only need to ensure that we can sketch f on this subspace which we denote as A. On
this subspace f is isomorphic to an OR function (up to taking negations of some of the variables)
and hence can be sketched using O(log 1/δ) uniformly random sketches with probability 1 − δ/2.
For the OR-function existence of the desired protocol is clear since we just need to verify whether
there exists at least one coordinate of the input that is set to 1. In case it does exist a random
sketch contains this coordinate with probability 1/2 and hence evaluates to 1 with probability at
least 1/4. Repeating O(log 1/δ) times the desired guarantee follows.

C

Tightness of Theorem 3.4 for the Majority function

An important question is whether Part 3 of Theorem 3.4 is tight. In particular, one might ask
whether the dependence on the error probability can be improved by replacing ∆d (f ) with a larger
quantity. As we show below this is not the case and hence Part 3 of Theorem 3.4 is tight.
We consider the majority function M ajn where n is an odd number. The total Fourier
weight on Fourier coefficients corresponding vectors of Hamming weight k is denoted as W k (f ) =

P
2 3/2
ˆ 2
α : kαk0 =k f (α) . For the majority function it is well-known (see e.g. [O’D14]) that for ξ = π
and odd k it holds that:
W k (M ajn ) = ξk −3/2 (1 ± O(1/k)).
Since M ajn is a symmetric function whose spectrum decreases monotonically with the Hamming
weight of the corresponding Fourier coefficient by a normalization argument as in Lemma 4.9
among all linear subspaces of dimension d the maximum Fourier weight is achieved by the standard
subspace Sd which spans d unit vectors. Computing the Fourier weight of Sn−1 we have:
X
X
[
[
M
aj n (α)2
M
aj n (α)2 = 1 −
α∈Sn−1

α∈S
/ n−1

n/2−1

=1−

X

W

2i+1

i=0

n/2−1

X

(M ajn )



n−1
2i 
n
2i+1

1
2i + 1
=1−
ξ
3/2
n
(2i + 1)
i=0


γ
1
=1− √ ±O
,
3/2
n
n



1±O



1
2i + 1



where γ > 0 is an absolute constant. Thus, we can set ǫn (M ajn ) = 1, ǫn−1 (M ajn ) = 1 −

O(1/n3/2 )

in Part 3 of Theorem 3.4. This gives the following corollary:

√γ
n

−



1
Corollary C.1. It holds that Dδ→,U (M ajn+ ) ≥ n, where δ = √γn + O n3/2
for some constant
γ > 0.
√
Tightness follows from the fact that error O(1/ n) for M ajn can be achieved using a trivial
(n−1)-bit protocol in which Alice sends the first n−1 bits of her input x1 , . . . , xn−1 and Bob outputs
M ajn−1 (x1 + y1 , x2 + y2 , . . . , xn−1 + yn−1 ). The only inputs on which this protocol can make an
33

error are inputs where there is an equal number of zeros and ones among x1 + y1 , . . . , xn−1 + yn−1 .
√
It follows from the standard approximation of binomials that such inputs are an O(1/ n) fraction
under the uniform distribution.

34

