Plaintext
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2020
Sign-Rank vs. Discrepancy
Hamed Hatami∗ Kaave Hosseini† Shachar Lovett‡
Received August 11, 2020; Revised May 2, 2022; Published July 9, 2022
Abstract. Sign-rank and discrepancy are two central notions in communication
complexity. The seminal paper by Babai, Frankl, and Simon (FOCS’86) initiated
an active line of research that investigates the gap between these two notions. In
this article, we establish the strongest possible separation by constructing a boolean
matrix whose sign-rank is only 3, and yet its discrepancy is 2−Ω(𝑛) . We note that
every matrix of sign-rank 2 has discrepancy 𝑛 −𝑂(1) .
In connection with learning theory, our result implies the existence of Boolean
matrices whose entries are represented by points and half-spaces in dimension
3, and yet, the normalized margin of any such representation (angle between the
half-spaces and the unit vectors representing the points), even in higher dimensions,
is very small.
In the context of communication complexity, our result in particular implies that
there are boolean functions with 𝑂(1) unbounded-error randomized communication
complexity while having Ω(𝑛) weakly unbounded-error randomized communication
complexity.
A conference version of this paper appeared in the Proceedings of the 35th Computational Complexity Conference,
2020 (CCC’20) [16].
∗ Supported by an NSERC grant.
† Supported by NSF grant CCF-1614023
‡ Supported by NSF grant CCF-1614023
ACM Classification: F.2.3
AMS Classification: 68Q11
Key words and phrases: communication complexity, sign-rank, discrepancy
© 2022 Hamed Hatami, Kaave Hosseini, and Shachar Lovett
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a019
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
1 Introduction
Sign-rank and discrepancy are arguably the most important analytic notions in the area of
communication complexity. Let 𝐴𝒳×𝒴 be a matrix with {−1, 1} entries (we refer to these
matrices as boolean matrices in this paper). The discrepancy of 𝐴 is the minimum over all input
distributions of the maximum correlation that 𝐴 has with a rectangle. More formally,
Disc(𝐴) B min max 𝔼(𝑥,𝑦)∼𝜈 [𝐴 𝑥,𝑦 1𝑆 (𝑥)1𝑇 (𝑦)] , (1.1)
𝜈 𝑆⊆𝒳
𝑇⊆𝒴
where the minimum is over all probability distributions 𝜈 on 𝒳 × 𝒴.
The classical concept1 of discrepancy was applied to Hadamard matrices (boolean matrices
with orthogonal rows) by Brown and Spencer2 in 1971 [6] to analyze the Gale—Berlekamp
switching game (see [13, Ch. 15]). Adapting their method, Chor and Goldreich [11] applied
discrepancy to randomized communication complexity. In deterministic communication
complexity, discrepancy was used by Babai, Nisan, and Szegedy [3] to prove lower bounds
for the deterministic communication complexity of Generalized Inner Product (GIP) in the
number-on-the-forehead model. Nowadays, discrepancy has become one of the most commonly
used measures in communication complexity, especially to prove lower bounds for randomized
protocols.
The sign-rank of 𝐴, denoted by rk± (𝐴), is the minimal rank of a real matrix whose entries
have the same sign pattern as 𝐴. This natural and fundamental notion was first introduced by
Paturi and Simon [22] in the context of the unbounded-error communication complexity. Since
then, its applications have extended beyond communication complexity to areas such as circuit
complexity [8, 23], learning theory [18–20], and even connections to algebraic geometry [29].
Boolean matrices in communication complexity correspond to boolean functions: given an
𝑛-bits two-player function 𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1}, it corresponds to the 2𝑛 × 2𝑛 matrix
𝐴 𝑥,𝑦 = 𝑓 (𝑥, 𝑦). The notions of discrepancy and sign-rank for 𝑓 are defined as the respective
quantities assigned to the corresponding matrix.
Our work is motivated by the following main informal question.
Problem 1.1. Does every function of low sign-rank have an efficient randomized protocol?
If the answer is negative, then the next question is, does it at least have large discrepancy.
(Small discrepancy is one technique to prove randomized communication complexity lower
bounds, but there are functions showing separations between the two measures, for example
set-disjointness [9].)
Problem 1.2. Does every function of low sign-rank have large discrepancy?
In order to build some intuition towards more quantitative questions, let us consider some
well-known examples:
1Bernard Chazelle writes in the Preface of his book “The Discrepancy Method” [10]: “Discrepancy theory grew
out of a question posed by van der Corput [12] in 1935: ‘How uniform can an infinite sequence in [0, 1] be?’ ‘’
2Erdős and Spencer credit the key lemma to J. H. Lindsey (John Hathway Lindsey II).
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 2
S IGN - RANK VS . D ISCREPANCY
• Greater-than: we interpret 𝑥, 𝑦 as integers in {1, . . . , 2𝑛 } and define 𝑓 (𝑥, 𝑦) = 1 if 𝑥 ≤ 𝑦
and 𝑓 (𝑥, 𝑦) = −1 otherwise. This function has sign-rank 2 and requires Θ(log 𝑛) bits of
randomized communication [21]. Moreover, its discrepancy is 𝑛 −Θ(1) , which proves the
communication lower bound.
• Set-disjointness: we interpret 𝑥, 𝑦 as subsets of [𝑛], and define 𝑓 (𝑥, 𝑦) = 1 if 𝑥, 𝑦 are
disjoint and 𝑓 (𝑥, 𝑦) = −1 otherwise. This function has sign-rank 𝑂(𝑛) and requires
communication complexity of Θ(𝑛) bits. However, this cannot be shown using discrepancy,
as the discrepancy of set-disjointness is 𝑛 −𝑂(1) [9].
• Sherstov [27] constructed a function with sign-rank 𝑂(𝑛) and discrepancy 2−Ω(𝑛) .
Thus, it seems that functions with logarithmic sign-rank can already be very complicated,
both in terms of their randomized communication complexity and also in terms of their
discrepancy. However, the situation is less clear for functions of constant sign-rank.
Problem 1.3. Does every function of constant sign-rank have an efficient randomized protocol?
In particular, does it have large discrepancy?
Our main result is a resounding no, already for sign-rank 3.
Theorem 1.4 (Main Theorem). There exists a function 𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1} of sign-rank 3
and discrepancy 𝑂(𝑛 · 2−𝑛/8 ) = 2−Ω(𝑛) .
Note that, it follows from the bound on discrepancy that the function 𝑓 in Theorem 1.4 has
Ω(𝑛) randomized communication complexity.
The sign-rank 3 in Theorem 1.4 is tight. We show in Section 3 that functions of sign-rank 1
or 2 are very simple combinatorially, and in particular have discrepancy 𝑛 −𝑂(1) and randomized
communication complexity 𝑂(log 𝑛).
The function 𝑓 in Theorem 1.4 is simple to define: the sign on an inner product in dimension
3. Concretely, let 𝑀 ≈ 2𝑛/3 . Alice gets a vector a ∈ [−𝑀, 𝑀]3 and Bob gets a vector b ∈ [−𝑀, 𝑀]3 .
Define
𝑓 (a, b) = signha, bi,
where sign : ℝ → {−1, 1} is the sign function, mapping positive inputs to 1 and zero or negative
inputs to −1; and h·, ·i is inner product over the integers. It is obvious from the definition that 𝑓
has sign-rank 3. We prove that its discrepancy is exponentially small. The actual function we
study is a mild restriction of this function, convenient for the proof. See Theorem 1.9 for details.
1.1 Connections to learning theory
Note that the sign-rank of an 𝑁 × 𝑁 boolean matrix 𝐴 is the smallest 𝑑 such that there exist unit
vectors 𝑢𝑖 , 𝑣 𝑗 ∈ ℝ 𝑑 with 𝐴 𝑖,𝑗 = sign(h𝑢𝑖 , 𝑣 𝑗 i) for all 𝑖, 𝑗 ∈ [𝑁]. These unit vectors 𝑢𝑖 , 𝑣 𝑗 represent
𝐴 as points and half-spaces in the 𝑑-dimensional space: 𝐴 𝑖,𝑗 = 1 iff the point 𝑢𝑖 belongs to the
half-space {𝑧 : h𝑧, 𝑣 𝑗 i > 0}.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 3
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
The geometric representations of boolean matrices as points and half-spaces is central to the
theory of learning. In this context, every column 𝑗 of 𝐴 corresponds to an object in some domain.
The vectors 𝑣 𝑗 ∈ ℝ 𝑑 , which are called feature vectors, represent each object by 𝑑 numerical features.
A classification algorithm receives as input a sample (𝑗1 , 𝐴 𝑖,𝑗1 ), . . . , (𝑗𝑚 , 𝐴 𝑖,𝑗𝑚 ) for an unknown 𝑖,
and its task is to predict 𝐴 𝑖,𝑗 for other values of 𝑗. For example, linear classifiers, such as support
vector machines, aim to produce from the samples a vector 𝑢 such that sign(h𝑢, 𝑣 𝑗 i) is a good
predictor of 𝐴 𝑖,𝑗 = sign(h𝑢𝑖 , 𝑣 𝑗 i).
While sign-rank optimizes the dimension (i. e., the number of features), there is a second
natural parameter that is associated with such representations. The quantity min𝑖,𝑗 |h𝑢𝑖 , 𝑣 𝑗 i| is
called the margin; it measures the smallest distance between the points 𝑢𝑖 and the hyperplanes
defined by 𝑣 𝑗 .
The margin of an 𝑁 × 𝑁 boolean matrix 𝐴, denoted by m(𝐴), is the largest possible margin
attainable by such representations. More formally,
m(𝐴) B sup min h𝑢𝑖 , 𝑣 𝑗 i ,
𝑖,𝑗
where the supremum is over all 𝑑 ∈ ℕ and unit vectors 𝑢𝑖 , 𝑣 𝑗 ∈ ℝ 𝑑 with 𝐴 𝑖,𝑗 = sign(h𝑢𝑖 , 𝑣 𝑗 i).
Dimension and margin are two important parameters that impact the performance of these
algorithms. It is desirable to represent the matrix 𝐴 in a smaller dimension and with a large
margin. Therefore, the problem of understanding the relation between sign-rank and margin is
an important one. Note that sign-rank minimizes the dimension while allowing the margin to
be arbitrarily small, and in contrast, margin maximizes the margin of the representation while
allowing the dimension to be arbitrarily large.
Due to the mentioned connections to the theory of learning, the notion of margin had been
mainly studied in that context, but Linial and Shraibman [20] proved that margin is essentially
equivalent to discrepancy:
Disc(𝐴) ≤ m(𝐴) ≤ 8 Disc(𝐴).
In light of this equivalence, our main result (Theorem 1.4) can be reformulated as the following.
Theorem 1.5 (Reformulation of Theorem 1.4). There exists 𝑁 × 𝑁 matrices 𝐴 with sign-rank 3 and
margin 𝑂(log(𝑁)/𝑁 1/8 ).
In other words, even though it is possible to represent 𝐴 in dimension 3, any representation
of 𝐴 in any dimension will have a very small margin.
It is worthwhile to contrast Theorem 1.5 with Forster’s seminal lower bound for sign-rank [14].
Forster proved that in the representation 𝐴 𝑖,𝑗 = sign(h𝑢𝑖 , 𝑣 𝑗 i) by unit vectors 𝑢𝑖 , 𝑣 𝑗 ∈ ℝ 𝑑 , it is
possible to transform the vectors so that the vectors 𝑣 𝑗 are in a so-called isotropic position. This
in particular implies
1
𝔼𝑖,𝑗∈[𝑁] |h𝑢𝑖 , 𝑣 𝑗 i| ≥ 𝔼𝑖,𝑗∈[𝑁] |h𝑢𝑖 , 𝑣 𝑗 i| 2 = .
𝑑
In other words, when sign-rank is small, there are representations with large “average” margin.
In the specific case of the matrix 𝐴 in Theorem 1.5, there exists a representation of 𝐴 with unit
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 4
S IGN - RANK VS . D ISCREPANCY
vectors 𝑢𝑖 , 𝑣 𝑗 ∈ ℝ3 such that
1
,
𝔼𝑖,𝑗∈[𝑁] |h𝑢𝑖 , 𝑣 𝑗 i| ≥
3
while Theorem 1.5 shows that in any representation (in any dimension), we have
min |h𝑢𝑖 , 𝑣 𝑗 i| ≤ 𝑂(log(𝑁)/𝑁 1/8 ).
𝑖,𝑗∈[𝑁]
Finally, let us mention that regarding the converse direction of the relation between sign-rank
and margin, Linial, Mendelson, Schechtman, and Shraibman [19, Corollary 3.2, Lemma 4.2, and
Section 8] proved the inequality rk± (𝐴) ≤ m(𝐴)−2 · log(𝑁), and asked whether the log factor in
this inequality is necessary. In fact the following question remains open.
Question 1.6. Is there a function 𝜂 such that for every boolean matrix 𝐴, we have rk± (𝐴) ≤
𝜂(m(𝐴)−1 )?
1.2 Connections to communication complexity
Theorem 1.4 is motivated by its applications in communication complexity. Consider a
communication problem 𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1} in Yao’s two party model. Given an error
parameter 𝜖 ∈ [0, 1/2], let 𝑅 𝜖 ( 𝑓 ) be the smallest communication cost of a private-coin randomized
communication protocol that on every input produces the correct answer with probability at
least 1 − 𝜖. Here private-coin refers to the assumption that players each have their own unlimited
private source of randomness. Three natural complexity measures arise from 𝑅 𝜖 ( 𝑓 ).
1. The quantity 𝑅 1/3 ( 𝑓 ) is called the bounded-error randomized communication complexity of 𝑓 .
The particular choice of 1/3 is not important as long as one is concerned with an error
that is bounded away from both 0 and 1/2 since in this case the error can be reduced by
running the protocol constantly many times and outputting the majority answer.
2. The weakly unbounded-error randomized communication complexity of 𝑓 is defined as
1
PP( 𝑓 ) = inf 𝑅 𝜖 ( 𝑓 ) + log ,
0≤𝜖≤1/2 1 − 2𝜖
that includes an additional penalty term, which increases as 𝜖 approaches 12 . The purpose
of this error term is to capture the range where 𝜖 is “moderately” bounded away from 12 .
3. Finally the unbounded-error communication complexity of 𝑓 is defined as the smallest
communication cost of a private-coin randomized communication protocol that computes
every entry of 𝑓 with an error probability that is strictly smaller than 12 . In other words,
the protocol only needs to outdo a random guess, which is always correct with probability
1
2 . We have
UPP( 𝑓 ) = lim 𝑅 𝜖 ( 𝑓 ).
𝜖→ 12 −0
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 5
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
In their seminal paper, Babai, Frankl and Simon [2] associated a complexity class to each
measure of communication complexity. While in the theory of Turing machines, a complexity
that is polynomial in the size of input bits is considered efficient, in the realm of communication
complexity, poly-logarithmic complexity plays this role, and communication complexity classes
are defined accordingly. Here, the communication complexity classes BPPcc , PPcc , and UPPcc
correspond to the class of communication problems { 𝑓𝑛 }∞ 𝑛=0
with polylogarithmic 𝑅1/3 ( 𝑓𝑛 ),
PP( 𝑓𝑛 ), and UPP( 𝑓𝑛 ), respectively.
Note that while BPPcc requires a strong bound on the error probability, and UPPcc only
requires an error that beats the random guess, PPcc corresponds to the natural requirement that
the protocol beats the 12 bound by a margin that is quasi-polynomially large. That is, PPcc is
the class of communication problems 𝑓𝑛 that satisfy 𝑅 1 −2− log𝑐 (𝑛) ( 𝑓𝑛 ) ≤ log𝑐 (𝑛) for some positive
2
constant 𝑐. We have the containment BPPcc ⊆ PPcc ⊆ UPPcc .
It turns out that both UPP( 𝑓 ) and PP( 𝑓 ) have elegant algebraic formulations. Paturi and
Simon [22] proved that UPP essentially coincides with the sign-rank of 𝑓 :
log rk± ( 𝑓 ) ≤ UPP( 𝑓 ) ≤ log rk± ( 𝑓 ) + 2.
Similarly to the way that sign-rank captures the complexity measure UPP( 𝑓 ), discrepancy
captures PP( 𝑓 ). The classical result relating randomized communication complexity and
discrepancy, due to Chor and Goldreich [11], is the inequality
1 − 2𝜖
𝑅 𝜖 ( 𝑓 ) ≥ log .
Disc( 𝑓 )
This in particular implies PP( 𝑓 ) ≥ − log Disc( 𝑓 ). Klauck [17] showed that the opposite is also
true; more precisely, that
PP( 𝑓 ) = 𝑂 − log Disc( 𝑓 ) + log(𝑛) .
Thus, a direct corollary of Theorem 1.4 is the following separation between unbounded-error
and weakly bounded-error communication complexity.
Corollary 1.7. There exists a function 𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1} with UPP( 𝑓 ) = 𝑂(1) and
PP( 𝑓 ) = Ω(𝑛).
1.3 Implications regarding approximate rank
Another closely related notion to sign-rank is approximate rank. Given 𝛼 > 1, the 𝛼-approximate
rank of a boolean matrix 𝐴 is the minimal rank of a real matrix 𝐵, of the same dimensions
as 𝐴, that satisfies 1 ≤ 𝐴 𝑖,𝑗 𝐵 𝑖,𝑗 ≤ 𝛼 for all 𝑖, 𝑗. The 𝛼-approximate rank of a boolean function
𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1} is the 𝛼-approximate rank of the associated 2𝑛 × 2𝑛 boolean
matrix. Observe that
rk± ( 𝑓 ) = lim rk𝛼 ( 𝑓 ).
𝛼→∞
Given this, a natural question is whether sign-rank can be separated from 𝛼-approximate rank.
This is also a consequence of Theorem 1.4.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 6
S IGN - RANK VS . D ISCREPANCY
Corollary 1.8. There exists a function 𝑓 : {0, 1} 𝑛 × {0, 1} 𝑛 → {−1, 1} with rk± ( 𝑓 ) = 3 and
rk𝛼 ( 𝑓 ) = Ω(2𝑛/4 /(𝛼𝑛)2 ) for any 𝛼 > 1.
Corollary 1.8 follows from Theorem 1.4 and the fact that
rk𝛼 ( 𝑓 ) ≥ Ω 𝛼−2 Disc( 𝑓 )−2 ,
which is established in [15, Equation (1)].
1.4 Related work
The question of separating sign-rank from discrepancy (or equivalently, separating unbounded-
error from weakly-unbounded-error communication complexity) has been studied in a number
of papers.
When Babai et al. [2] introduced the complexity classes BPPcc ⊆ PPcc ⊆ UPPcc , they noticed
that the set-disjointness problem separates BPPcc from PPcc , but they left open the question of
separating UPPcc from PPcc , or equivalently sign-rank from discrepancy. This question remained
unanswered for more than two decades until finally Buhrman et al. [7] and independently
Sherstov [24] showed that there are √ 𝑛-bit boolean functions 𝑓 such that UPP( 𝑓 ) = 𝑂(log 𝑛) but
PP( 𝑓 ) = Ω(𝑛 1/3 ) and PP( 𝑓 ) = Ω( 𝑛), respectively. The bounds on PP( 𝑓 ) were strengthened
in subsequent work [25–28] with the final recent separation from [27] giving a function 𝑓
with UPP( 𝑓 ) = 𝑂(log 𝑛) and maximal possible PP( 𝑓 ) = Ω(𝑛). Despite this line of work, no
improvement was made on the 𝑂(log(𝑛)) bound on UPP( 𝑓 ). In fact, to the best of our knowledge,
prior to this work, it was not even known whether there are functions with UPP( 𝑓 ) = 𝑂(1)
and 𝑅1/3 ( 𝑓 ) = 𝜔(log(𝑛)). To recall, Corollary 1.7 gives a function 𝑓 with UPP( 𝑓 ) = 𝑂(1) and
PP( 𝑓 ) = Ω(𝑛).
A different aspect is the study of sign-rank of matrices. Matrices of sign-rank 1 and 2 are
simple combinatorially, while matrices with sign-rank 3 seem to be much more complex. First,
it turns out that deciding whether a matrix has sign-rank 3 is NP-hard, a result that was shown
by Basri et al. [4] and independently by Bhangale and Kopparty [5]. In fact, deciding if a matrix
has sign-rank 3 is ∃ℝ-complete, where ∃ℝ is the existential first-order theory of the reals, a
complexity class lying between NP and PSPACE. This ∃ℝ-completeness result is implicit in
both [4] and [5], as observed by [1].
1.5 Proof overview
We give an overview of the proof of Theorem 1.4. Let us first slightly modify 𝑓 in a way that
will be convenient for the proof.
Let 𝑁 ≈ 2𝑛/4 . Alice gets three integers 𝑥 1 , 𝑥2 , 𝑧 and Bob gets two integers 𝑦1 , 𝑦2 , where
𝑥 1 , 𝑥2 , 𝑦1 , 𝑦2 ∈ [𝑁] and 𝑧 ∈ [−3𝑁 2 , 3𝑁 2 ]. We shorthand 𝑥 = (𝑥 1 ; 𝑥 2 ) and 𝑦 = (𝑦1 ; 𝑦2 ), so that
Alice’s input is (𝑥; 𝑧) and Bob’s input is 𝑦. Note that 𝑥, 𝑦 ∈ [𝑁]2 . Define
𝑓 ([𝑥, 𝑧], 𝑦) = sign(𝑧 − h𝑥, 𝑦i) = sign(𝑧 − 𝑥1 𝑦1 − 𝑥2 𝑦2 ).
The following is our main technical result.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 7
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Theorem 1.9 (Main result; technical version). Let 𝑓 be as above. Then Disc( 𝑓 ) = 𝑂(𝑛 · 2−𝑛/8 ).
We remark that the function 𝑓 here is a restriction of the function 𝑓 described after
Theorem 1.4, and therefore, Theorem 1.9 implies Theorem 1.4.
To prove Theorem 1.9, it is useful to think about our discrepancy bound in the language
of communication complexity. We prove Theorem 1.9 in two steps. Below we denote random
variables with bold letters.
Step 1: constructing a hard distribution First, we define a hard distribution 𝜈. Alice and
Bob receive uniformly random integers x, y ∈ [𝑁]2 respectively where 𝑁 ≈ 2𝑛/4 . The inner
product hx, yi is a random variable over [2𝑁 2 ]. Alice also receives another random variable
z over [−3𝑁 2 , 3𝑁 2 ], whose distribution we will explain shortly. The players want to decide
whether hx, yi ≥ z. We define z in such a way that
• hx, yi − z ∈ [−2𝑁 , 2𝑁),
• hx, yi ≥ z happens with probability 12 ,
• The distribution of z conditioned on hx, yi ≥ z is extremely close in total variation distance
to the distribution of z conditioned on hx, yi < z, even when restricted to arbitrary large
combinatorial rectangles. This is formalized in Lemma 4.1 and calculations preceding it.
See step 2 bellow for more discussion.
To construct z, we first define another independent random variable k and then let z = hx, yi + k,
or z = hx, yi + k − 2𝑁, with equal probabilities. We choose k = k1 + k2 for k1 , k2 independent
uniform elements from [𝑁] so that k is smooth enough for the analysis to go through. Note that
the range of z is really just [−2𝑁 , 2𝑁 2 + 2𝑁], and we picked the range of 𝑧 in the definition of 𝑓
as 𝑧 ∈ [−3𝑁 2 , 3𝑁 2 ] for its simpler shape.
Step 2: translation invariance of hx, yi + k We bound the discrepancy Disc𝜈 ( 𝑓 ) as follows. Fix
a combinatorial rectangle 𝐴 × 𝐵 ⊂ ([𝑁]2 × [−3𝑁 2 , 3𝑁 2 ]) × [𝑁]2 . We bound the correlation of 𝑓
with 1𝐴 1𝐵 under the distribution 𝜈. In other words, we show under the distribution 𝜈, restricted
to the rectangle 𝐴 × 𝐵, we have 𝜈( 𝑓 −1 (1)) ≈ 𝜈( 𝑓 −1 (−1)). This boils down to showing that after
conditioning on the input being in 𝐴 × 𝐵, the distribution of (hx, yi + k)| 𝐴,𝐵 has small total
variation distance with (hx, yi + k − 2𝑁)| 𝐴,𝐵 . We prove a stronger statement, and show that in
fact this is true even if we fix x = 𝑥 to a typical 𝑥 (and therefore choosing 𝐴 ⊂ {𝑥} × [−3𝑁 2 , 3𝑁 2 ]),
namely, after conditioning x = 𝑥, and y ∈ 𝐵, the distribution of (hx, yi + k)| y∈𝐵 has small total
variation distance with its translation by 2𝑁. To prove the claim we appeal to Fourier analysis
and estimate the Fourier coefficients of the random variable, and verify that the only potentially
large Fourier coefficients correspond to Fourier characters that are almost invariant under
translations by 2𝑁. Computing these Fourier coefficients involves computing some partial
exponential sums whose details may be seen in Lemma 4.3 and Lemma 4.4. At a high level,
these boil down to showing that if x, y ∈ ℤ2𝑝 are two random independent variables, uniform
over large sets, then their inner product hx, yi has well-behaved spectral properties.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 8
S IGN - RANK VS . D ISCREPANCY
Paper organization. We give preliminary definitions needed for the proof in Section 2. We
discuss the structure of matrices of sign-rank 1 and 2 in Section 3. We prove our main result,
Theorem 1.9, in Section 4.
2 Preliminaries
Notation. To simplify the presentation, we often use . or ≈ instead of the big-𝑂 notation.
That is, 𝑥 . 𝑦 means 𝑥 = 𝑂(𝑦), and 𝑥 ≈ 𝑦 means 𝑥 = Θ(𝑦). For integers 𝑁 ≤ 𝑀 we denote
[𝑁 , 𝑀] = {𝑁 , . . . , 𝑀}, and we shorthand [𝑁] = [1, 𝑁].
Discrepancy. Let 𝒳, 𝒴 be finite sets, and 𝜈 be a probability distribution on 𝒳 × 𝒴. The
discrepancy of a function 𝑓 : 𝒳 × 𝒴 → {−1, 1} with respect to 𝜈 and a combinatorial rectangle
𝐴 × 𝐵 ⊆ 𝒳 × 𝒴 is defined as
Disc𝐴×𝐵
𝜈 ( 𝑓 ) = 𝔼(x,y)∼𝜈 [ 𝑓 (x, y)1𝐴 (x)1𝐵 (y)] .
The discrepancy of 𝑓 with respect to 𝜈 is defined as
Disc𝜈 ( 𝑓 ) = max Disc𝐴×𝐵
𝜈 ( 𝑓 ),
𝐴,𝐵
and finally the discrepancy of 𝑓 is defined as
Disc( 𝑓 ) = min Disc𝜈 ( 𝑓 ).
𝜈
Probability. We denote random variables with bold letters. Given a random variable r, let
𝜇 = 𝜇r denote its distribution. The conditional distribution of r, conditioned on r ∈ 𝑆 for some
set 𝑆, is denoted by 𝜇| 𝑆 . Given a finite set 𝑆, we denote the uniform measure on 𝑆 by 𝜇𝑆 . If r is
uniformly sampled from 𝑆, we denote it by r ∼ 𝑆.
Fourier analysis. The proof of Theorem 1.9 is based on Fourier analysis over cyclic groups.
Next we introduce the relevant notation. Let 𝑝 be a prime. For 𝑓 , 𝑔 : ℤ𝑝 → ℂ define
1 Õ
h 𝑓 , 𝑔i = 𝑓 (𝑥)𝑔(𝑥),
𝑝
𝑥∈ℤ𝑝
and
1 Õ
𝑓 ∗ 𝑔(𝑧) = 𝑓 (𝑥)𝑔(𝑧 − 𝑥).
𝑝
𝑥∈ℤ𝑝
Let e𝑝 : ℤ𝑝 → ℂ denote the function e𝑝 : 𝑥 ↦→ e2𝜋𝑖𝑥/𝑝 . For 𝑎 ∈ ℤ𝑝 define the character
𝜒 𝑎 : 𝑥 ↦→ e𝑝 (−𝑎𝑥). The Fourier expansion of 𝑓 : ℤ𝑝 → ℂ is the sum
Õ
𝑓 (𝑥) = 𝑓 (𝑎)𝜒 𝑎 (𝑥),
b
𝑎∈ℤ𝑝
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 9
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
𝑓 (𝑎) = h 𝑓 , 𝜒 𝑎 i. Note that by definition,
where b
1 Õ
𝑓 (𝑎) =
b 𝑓 (𝑥)e𝑝 (𝑎𝑥).
𝑝
𝑥∈ℤ𝑝
It follows from the properties of the characters that
Õ
𝑓 ∗ 𝑔(𝑧) = 𝑓 (𝑎)b
b 𝑔 (𝑎)𝜒 𝑎 (𝑧),
𝑎∈ℤ𝑝
showing that 𝑓 ∗ 𝑔(𝑎) = b
𝑓 (𝑎)b
𝑔 (𝑎). In particular, if x1 , . . . , x 𝑘 are independent random variables
taking values in ℤ𝑝 , and if x = x1 + . . . + x 𝑘 , then
𝑘
Ö
𝜇bx (𝑎) = 𝑝 𝑘−1 𝜇
cx𝑖 (𝑎).
𝑖=1
Number theory estimates. Fix a prime 𝑝. Given an integer 𝑥, we denote the distance of 𝑥 to
the closest multiple of 𝑝 (and abusing standard notation) by
k𝑥 k 𝑝 = min{|𝑥 − 𝑧𝑝| : 𝑧 ∈ ℤ}.
We will often use the estimate
k𝑥 k 𝑝
|e𝑝 (𝑥) − 1| ≈ ,
𝑝
which follows from the easy estimate that 4|𝑦| ≤ |e2𝜋𝑖 𝑦 − 1| ≤ 8|𝑦| for 𝑦 ∈ [−1/2, 1/2], and taking
sign(𝑥)k𝑥k 𝑝
𝑦= 𝑝 .
3 Sign-rank 1 and 2
In this section we demonstrate that boolean matrices with sign-rank 1 or 2 are very simple
combinatorially. Let 𝐴 be an 𝑁 × 𝑁 boolean matrix for 𝑁 = 2𝑛 . If 𝐴 has sign-rank 1, then there
exist nonzero numbers 𝑎 1 , . . . , 𝑎 𝑁 , 𝑏1 , . . . , 𝑏 𝑁 ∈ ℝ such that 𝐴 𝑖,𝑗 = sign(𝑎 𝑖 𝑏 𝑗 ). In particular, if we
partition the 𝑎 𝑖 and the 𝑏 𝑗 to the positive and negative numbers, we see that 𝐴 can be partitioned
into 4 monochromatic submatrices. This implies that Disc(𝐴) = Ω(1).
Assume next that 𝐴 has sign-rank 2. Then there exist vectors 𝑢1 , . . . , 𝑢𝑁 , 𝑣1 , . . . , 𝑣 𝑁 ∈ ℝ2
such that 𝐴 𝑖,𝑗 = sign(h𝑢𝑖 , 𝑣 𝑗 i). By applying a rotation to the vectors, we may assume that their
coordinates are all nonzero. Next, by scaling the vectors, we may assume that 𝑢𝑖 = (±1, 𝑎 𝑖 ) and
𝑣 𝑗 = (𝑏 𝑗 , ±1) for all 𝑖, 𝑗. Next, partition the 𝑎 𝑖 and the 𝑏 𝑗 to the positive and negative numbers.
Consider without loss of generality the submatrix in which 𝑢𝑖 = (−1, 𝑎 𝑖 ) and 𝑣 𝑗 = (𝑏 𝑗 , 1) for all
𝑖, 𝑗 (the other three cases are equivalent). In this submatrix, 𝐴 𝑖,𝑗 = sign(𝑎 𝑖 − 𝑏 𝑗 ). By removing
repeated rows and columns, we get that the submatrix is an upper triangular matrix, with 1
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 10
S IGN - RANK VS . D ISCREPANCY
on or above the diagonal and −1 below the diagonal. That is, the submatrix is equivalent to
the matrix corresponding to the Greater-Than boolean function on at most 𝑛 bits. Nisan [21]
showed that the bounded-error communication complexity of this matrix is 𝑂(log 𝑛), which in
particular implies that the discrepancy is at least 𝑛 −𝑂(1) . This implies that also Disc(𝐴) ≥ 𝑛 −𝑂(1) .
4 Sign-rank 3 vs. discrepancy
We now turn to proving Theorem 1.9. To recall, Alice’s input is the pair (𝑥; 𝑧) with 𝑥 ∈ [𝑁]2 , 𝑧 ∈
[−3𝑁 2 , 3𝑁 2 ], and Bob’s input is 𝑦 ∈ [𝑁]2 . The hard distribution 𝜈 is defined as follows. First,
sample x, y uniformly and independently from [𝑁]2 . Next, sample k1 , k2 ∈ [𝑁] uniformly and
independently, and let k = k1 +k2 . Define z as follows: choose z = hx, yi +k or z = hx, yi +k−2𝑁,
each with probability 1/2. Observe that in the former case hx, yi < z and hence 𝑓 ((𝑥; 𝑧), y) = 1;
and in the latter case hx, yi ≥ z and hence 𝑓 ([x, z], y) = −1. Thus 𝑓 is balanced:
Pr[ 𝑓 ((𝑥; 𝑧), y) = 1] = Pr[ 𝑓 ((𝑥; 𝑧), y) = −1] = 1/2.
In order to prove the theorem, we bound the correlation of 𝑓 with a rectangle 𝐴 × 𝐵, where
𝐴 ⊆ [𝑁]2 × [−3𝑁 2 , 3𝑁 2 ] and 𝐵 ⊆ [𝑁]2 . For 𝑥 ∈ [𝑁]2 , let
𝐴 𝑥 = {𝑧 : [𝑥, 𝑧] ∈ 𝐴}.
We have
Disc𝐴×𝐵
𝜈 ( 𝑓 ) = 𝔼([x,z],y)∼𝜈 [ 𝑓 ([x, z], y)1𝐴 (x, z)1𝐵 (y)]
= 𝔼x,y∼[𝑁]2 1𝐵 (y) 𝔼z|x,y [ 𝑓 ([x, z], y)1𝐴x (z)] .
Recall the definition of 𝑓 and that z = hx, yi + k or z = hx, yi + k − 2𝑁 with equal probabilities.
In the former case 𝑓 evaluates to 1, and it the latter case it evaluates to −1. We thus have
1
Disc𝐴×𝐵
𝜈 (𝑓) = 𝔼x,y,k [ 𝑓 ([x, hx, yi + k], y)1𝐵 (y)1𝐴x (hx, yi + k)]
2
1
+ 𝔼x,y,k [ 𝑓 ([x, hx, yi + k − 2𝑁], y))1𝐵 (y)1𝐴x (hx, yi + k − 2𝑁)]
2
1
= 𝔼x,y,k [1𝐵 (y)1𝐴x (hx, yi + k) − 1𝐵 (y)1𝐴x (hx, yi + k − 2𝑁)]
2
|𝐵|
= 𝔼x 𝔼y∼𝐵 𝔼k [1𝐴x (hx, yi + k) − 1𝐴x (hx, yi + k − 2𝑁)] .
2𝑁 2
For 𝑥 ∈ [𝑁]2 let 𝜈𝑥𝐵 denote the distribution of hx, yi + k conditioned on x = 𝑥, y ∈ 𝐵. With this
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 11
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
notation,
|𝐵|
Disc𝐴×𝐵
𝜈 (𝑓) = 𝔼x 𝔼w∼𝜈x𝐵 [1𝐴x (w) − 1𝐴x (w − 2𝑁)]
2𝑁 2
|𝐵| Õ
= 𝔼x 1𝐴x (𝑤)𝜈x𝐵 (𝑤) − 1𝐴x (𝑤 − 2𝑁)𝜈x𝐵 (𝑤)
2𝑁 2 𝑤∈ℤ
|𝐵| Õ
= 𝔼x 1𝐴x (𝑤)𝜈x𝐵 (𝑤) − 1𝐴x (𝑤)𝜈x𝐵 (𝑤 + 2𝑁)
2𝑁 2 𝑤∈ℤ
|𝐵| Õ
≤ 2
𝔼x 𝜈x𝐵 (𝑤) − 𝜈x𝐵 (𝑤 + 2𝑁) ,
2𝑁 𝑤∈ℤ
which no longer depends on 𝐴. The random variable hx, yi + k is in the range [−3𝑁 2 , 3𝑁 2 ]
so we embed [−3𝑁 2 , 3𝑁 2 ] into ℤ𝑝 for some prime 𝑝 ∈ [6𝑁 2 + 1, 12𝑁 2 ]. We consider 𝜈𝑥𝐵 as a
distribution over ℤ𝑝 , and thus we can rewrite
𝑝|𝐵|
Disc𝐴×𝐵
𝜈 (𝑓) ≤ 𝔼x 𝔼w∼ℤ𝑝 |𝜈x𝐵 (w) − 𝜈x𝐵 (w + 2𝑁)|
2𝑁 2
. |𝐵| · 𝔼x 𝔼w∼ℤ𝑝 |𝜈x𝐵 (w) − 𝜈x𝐵 (w + 2𝑁)|.
The following lemma, whose proof is deferred to the next section, completes the proof.
Lemma 4.1. For all 𝑁˜ such that 𝑁˜ ≈ 𝑁,
log 𝑁
𝔼x 𝔼w∼ℤ𝑝 |𝜈x𝐵 (w) − 𝜈x𝐵 (w + 𝑁)|
˜ . p .
|𝐵|𝑁 3
By invoking Lemma 4.1 for 𝑁˜ = 2𝑁 we obtain
r
log 𝑁 |𝐵|
Disc( 𝑓 ) ≤ Disc𝐴×𝐵 ( 𝑓 ) . |𝐵| p log 𝑁 ≤ 𝑁 − 2 log 𝑁 . 𝑛2−𝑛/8 .
1
𝜈 ≤
|𝐵|𝑁 3 𝑁 3
4.1 Invariance of 𝜈x𝐵 under translation
The goal of this section is to prove Lemma 4.1. We will prove that for a typical 𝑥, the measure
𝜈𝑥𝐵 is almost invariant under the translations by 𝑁˜ ≈ 𝑁. First we compute the Fourier expansion
of this measure.
Lemma 4.2. For all 𝑥 ∈ [𝑁]2 and 𝑎 ∈ ℤ𝑝 , we have
1 e𝑝 (𝑁 𝑎) − 1
2
𝐵 1
𝜈 (𝑎) = e (2𝑎) e𝑝 (𝑎h𝑥, yi) .
c
𝑥 𝑝 𝔼 y∼𝐵
𝑝 𝑁 e𝑝 (𝑎) − 1
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 12
S IGN - RANK VS . D ISCREPANCY
Proof. Recall that 𝜈𝑥𝐵 is the distribution of h𝑥, yi +k1 +k2 where y ∼ 𝐵 and k1 , k2 ∼ [𝑁]. Therefore
for all 𝑎 ∈ ℤ𝑝 ,
𝜈 𝐵 (𝑎) = 𝑝 2 𝜇 (𝑎)𝜇c (𝑎)𝜇c (𝑎) = 𝑝 2 𝜇 (𝑎)𝜇d (𝑎)2 ,
c
𝑥 h𝑥,yi k1 k2 h𝑥,yi [𝑁]
where to recall 𝜇[𝑁] is the uniform distribution on [𝑁]. First, we compute the Fourier coefficients
of 𝜇h𝑥,yi :
1 Õ 1
𝜇 𝜇h𝑥,yi (𝑡)e𝑝 (𝑎𝑡) = 𝔼y∼𝐵 e𝑝 (𝑎h𝑥, 𝑦i) .
h𝑥,yi (𝑎) =
𝑝 𝑝
𝑡∈ℤ𝑝
Next, we compute the Fourier coefficients of 𝜇[𝑁] :
𝑁
1Õ 1 e𝑝 (𝑎) e𝑝 (𝑁 𝑎) − 1
𝜇d
[𝑁] (𝑎) = e𝑝 (𝑎𝑡) = · ,
𝑝 𝑁 𝑝𝑁 e𝑝 (𝑎) − 1
𝑡=1
where we have computed the partial sum of the geometric series {e𝑝 (𝑎𝑡)} 𝑡=1,...,𝑁 . The lemma
follows.
With the Fourier coefficients c𝜈𝑥𝐵 (𝑎) computed in Lemma 4.2, we can analyze the distance
𝐵 ˜
from 𝜈x to its translation by 𝑁 ≈ 𝑁.
Proof of Lemma 4.1. Let w ∼ ℤ𝑝 . Recall that x ∼ [𝑁]2 and that 𝑁˜ ≈ 𝑁. Using the Fourier
expansion of 𝜈x𝐵 we can write
Õ
𝑠 := 𝔼x,w |𝜈x𝐵 (w) − 𝜈x𝐵 (w + 𝑁)|
˜ = 𝔼x,w 𝜈 𝐵 (𝑎) 𝜒 (w) − 𝜒 (w + 𝑁)
c
x 𝑎
˜ . 𝑎
𝑎∈ℤ𝑝
𝜈x𝐵 (𝑎),
We may now use Lemma 4.2 and substitute the Fourier coefficient c
1 e𝑝 (𝑁 𝑎) − 1
Õ 2
1
𝑠 = 𝔼x,w 𝑒 𝑝 (2𝑎) 𝔼y∼𝐵 e𝑝 (𝑎hx, yi) (1 − e𝑝 (−𝑁˜ 𝑎))𝜒 𝑎 (w) .
𝑝 𝑁 e𝑝 (𝑎) − 1
𝑎∈ℤ𝑝
Squaring both sides, and applying Cauchy–Schwarz and then Parseval’s identity, we get
2
1 e𝑝 (𝑁 𝑎) − 1
Õ 2
𝑠 2 𝑝 2 ≤ 𝔼x,w (1 − e𝑝 (−𝑁˜ 𝑎))𝜒 𝑎 (w)
e𝑝 (2𝑎) 𝔼y∼𝐵 e𝑝 (𝑎hx, yi)
𝑁 e𝑝 (𝑎) − 1
𝑎∈ℤ𝑝
Õ 2 1 e𝑝 (𝑁 𝑎) − 1 4
|1 − e𝑝 (−𝑁˜ 𝑎)| 2
= 𝔼x 𝔼y∼𝐵 e𝑝 (𝑎hx, yi)
𝑁 e𝑝 (𝑎) − 1
𝑎∈ℤ𝑝
Õ 2 1 e𝑝 (𝑁 𝑎) − 1 4
|1 − e𝑝 (𝑁˜ 𝑎)| 2 .
= 𝔼x 𝔼y∼𝐵 e𝑝 (𝑎hx, yi)
𝑁 e𝑝 (𝑎) − 1
𝑎∈ℤ𝑝
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 13
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Recalling that 𝑝 ≈ 𝑁 2 , note that for 𝑎 ≠ 0 it holds that
k𝑁 𝑎k 𝑝
!
1 e𝑝 (𝑁 𝑎) − 1 𝑁
≈ . min 1,
𝑁 e𝑝 (𝑎) − 1 𝑁 k𝑎 k 𝑝 k𝑎k 𝑝
and
𝑁˜ 𝑎 𝑝
!
k𝑎 k 𝑝
|e𝑝 ( 𝑁˜ 𝑎) − 1| ≈ . min 1, ,
𝑝 𝑁
both of which follow from trivial upper bounds k𝑁 𝑎 k 𝑝 ≤ 𝑁 k𝑎k 𝑝 and k𝑥 k 𝑝 ≤ 𝑝 ≈ 𝑁 2 . Let us
denote 𝐸 𝑎 (𝐵) := 𝔼x 𝔼y∼𝐵 e𝑝 (𝑎hx, yi) . We break the sum into two parts and for each part use
2
a different estimate for 𝐸 𝑎 (𝐵) using Lemma 4.3 below.
1 e𝑝 (𝑁 𝑎) − 1
4
1 Õ ˜ 1 Õ
𝑠2 . 𝐸 𝑎 (𝐵)|e 𝑝 ( 𝑁 𝑎) − 1| 2
+ 𝐸 𝑎 (𝐵)
𝑝2 𝑝2 𝑁 e𝑝 (𝑎) − 1
k𝑎 k 𝑝 <𝑁 k𝑎 k 𝑝 ≥𝑁
!2 4 !
1 Õ k𝑎 k 𝑝 1 Õ 𝑁
. 𝐸 𝑎 (𝐵) + 2 𝐸 𝑎 (𝐵)
𝑝2 𝑁 𝑝 k𝑎k 𝑝
k𝑎 k 𝑝 <𝑁 k𝑎 k 𝑝 ≥𝑁
!2 2
!4
1 Õ 𝑁 2 log 𝑁 k𝑎 k 𝑝 1 Õ k𝑎 k 𝑝 log 𝑁 𝑁
2 2
. · + 2 ·
𝑝2 2 |𝐵| 𝑁 𝑝 𝑁2 |𝐵| k𝑎k 𝑝
k𝑎 k <𝑁 k𝑎 k 𝑝
𝑝 k𝑎 k 𝑝 ≥𝑁
log2 𝑁 © Õ 1 Õ 1 ª
. +
𝑁 2 |𝐵| 𝑁2
2
®
k𝑎k <𝑁 k𝑎 k ≥𝑁 k𝑎k 𝑝
« 𝑝 𝑝 ¬
!
log 𝑁
2
1 Õ 1
. 𝑁· 2+
𝑁 |𝐵|
2 𝑁 𝑡≥𝑁
𝑡2
log2 𝑁 1 log2 𝑁
. = .
𝑁 2 |𝐵| 𝑁 |𝐵|𝑁 3
4.2 Uniformity of product sets over ℤ𝑝
Recall that 𝐸 𝑎 (𝐵) := 𝔼x∼[𝑁]2 𝔼y∼𝐵 [𝜒 𝑎 (hx, yi)] . The following lemma provides estimates for it.
2
k𝑎k 2𝑝 log2 𝑁
Lemma 4.3. 𝐸 𝑎 (𝐵) . max , 𝑁
2
𝑁 2 k𝑎 k 2𝑝
· |𝐵|
.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 14
S IGN - RANK VS . D ISCREPANCY
Proof. We have
2
1 Õ
𝐸 𝑎 (𝐵) = 𝔼 x∼[𝑁]2 𝜒 𝑎 (hx, 𝑦i)
|𝐵| 2 𝑦∈𝐵
1 Õ
= 𝔼x∼[𝑁]2 𝜒 𝑎 (hx, 𝑦 0 − 𝑦 00i)
|𝐵| 2 𝑦0 ,𝑦00 ∈𝐵
1 Õ
≤ 𝔼x∼[𝑁]2 𝜒 𝑎 (hx, 𝑦 0 − 𝑦 00i) .
|𝐵| 2 𝑦0 ,𝑦00 ∈𝐵
Let 𝐵 − 𝐵 = {𝑦 0 − 𝑦 00 : 𝑦 0 , 𝑦 00 ∈ 𝐵} ⊂ ℤ2𝑝 . Any element 𝑦 ∈ 𝐵 − 𝐵 can be expressed as 𝑦 = 𝑦 0 − 𝑦 00
for 𝑦 0 , 𝑦 00 ∈ 𝐵 in at most |𝐵| ways. Thus we can bound
1 Õ
𝐸 𝑎 (𝐵) ≤ 𝔼x∼[𝑁]2 𝜒 𝑎 (hx, 𝑦i) .
|𝐵|
𝑦∈𝐵−𝐵
Since 𝐵 − 𝐵 ⊆ [𝑁]2 − [𝑁]2 ⊆ [−𝑁 , 𝑁]2 , we can simplify the above to
1 Õ Õ
𝐸 𝑎 (𝐵) ≤ 𝜒 𝑎 (h𝑥, 𝑦i)
𝑁 |𝐵|
2
𝑦∈[−𝑁 ,𝑁]2 𝑥∈[𝑁]2
1 Õ Õ
= 𝜒 𝑎 (𝑥 1 𝑦1 ) · 𝜒 𝑎 (𝑥 2 𝑦2 )
𝑁 |𝐵|
2
𝑦1 ,𝑦2 ∈[−𝑁 ,𝑁] 𝑥1 ,𝑥2 ∈[𝑁]
1 Õ Õ Õ
= 𝜒 𝑎 (𝑥 1 𝑦1 ) 𝜒 𝑎 (𝑥 2 𝑦2 )
𝑁 2 |𝐵|
𝑦1 ,𝑦2 ∈[−𝑁 ,𝑁] 𝑥1 ∈[𝑁] 𝑥2 ∈[𝑁]
2
1 © Õ Õ
= 𝜒 𝑎 (𝑥 𝑦) ®
ª
𝑁 |𝐵|
2
« 𝑦∈[−𝑁 ,𝑁] 𝑥∈[𝑁] ¬
2
1 © Õ Õ
. 𝜒 𝑎 (𝑥 𝑦) ® .
ª
𝑁 2 |𝐵|
« 𝑦∈[0,𝑁] 𝑥∈[𝑁] ¬
Note that for a fixed 𝑦 ≠ 0, 𝑥∈[𝑁] 𝜒 𝑎 (𝑥 𝑦) is a partial sum of a geometric series which satisfies
Í
e𝑝 (𝑁 𝑎 𝑦)−1
𝑥∈[𝑁] 𝜒 𝑎 (𝑥 𝑦)
Í
= e𝑝 (𝑎 𝑦)−1
, and hence
Õ Õ Õ e𝑝 (𝑁 𝑎 𝑦) − 1 Õ k𝑁 𝑎 𝑦 k 𝑝
𝜒 𝑎 (𝑥 𝑦) ≤ 𝑁 + .𝑁+ .
e𝑝 (𝑎 𝑦) − 1 k𝑎 𝑦k 𝑝
𝑦∈[0,𝑁] 𝑥∈[𝑁] 𝑦∈[𝑁] 𝑦∈[𝑁]
Invoking Lemma 4.4 below finishes the proof.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 15
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Lemma 4.4. Let 𝑝 ≥ 𝑁 2 be prime and let 𝑎 ∈ ℤ𝑝 \ {0}. Then
Õ k𝑁 𝑎 𝑦 k 𝑝 𝑝 log 𝑝
. .
k𝑎 𝑦k 𝑝 min(𝑁 , k𝑎k 𝑝 )
𝑦∈[𝑁]
We need the following simple claim in the proof of Lemma 4.4.
Claim 4.5. Let r be a random variable which takes values in [𝐾]. Let 𝑔 : [𝐾] → ℝ. Then
𝐾−1
Õ
𝔼r 𝑔(r) = 𝑔(𝐾) + (𝑔(𝑖) − 𝑔(𝑖 + 1)) Pr[r ≤ 𝑖] .
𝑖=1
Proof.
𝐾
Õ
𝔼r 𝑔(r) = 𝑔(𝑖) Pr[r = 𝑖]
𝑖=1
𝐾
Õ
= 𝑔(𝑖) (Pr[r ≤ 𝑖] − Pr[r ≤ 𝑖 − 1])
𝑖=1
𝐾−1
Õ
= 𝑔(𝐾) + (𝑔(𝑖) − 𝑔(𝑖 + 1)) Pr[r ≤ 𝑖] .
𝑖=1
Proof of Lemma 4.4. We separate the proof to two cases of k𝑎 k 𝑝 < 𝑁 and k𝑎 k 𝑝 ≥ 𝑁. Consider an
integer 𝑘 with k𝑎 k 𝑝 ≤ 𝑘 ≤ 𝑝. We start by estimating the size of the set
𝑆 𝑘 = {𝑦 ∈ [𝑁] : k 𝑦𝑎 k 𝑝 ≤ 𝑘}.
Note that if 𝑦 ∈ 𝑆 𝑘 , then 𝑦𝑎 ∈ 𝑝 ℎ + [−𝑘, 𝑘] for some integer ℎ ≥ 0. Since 𝑦 ∈ [𝑁], we have
𝑁 k𝑎 k 𝑝 +𝑘 𝑁 k𝑎k 𝑝
ℎ ≤ 𝑝 , and hence there are at most 𝑝 + 1 such values of ℎ. Fixing ℎ, we have
𝑝ℎ
𝑦 ∈ k𝑎 k 𝑝
+ [−𝑘/k𝑎k 𝑝 , 𝑘/k𝑎 k 𝑝 ], and there are at most k𝑎2𝑘k + 1 ≤ k𝑎3𝑘k such values of 𝑦. We
𝑝 𝑝
conclude that
𝑁 k𝑎 k 𝑝
!
3𝑘 3𝑁 𝑘 3𝑘 𝑘 𝑘
|𝑆 𝑘 | ≤ +1 × ≤ + . + .
𝑝 k𝑎 k 𝑝 𝑝 k𝑎k 𝑝 𝑁 k𝑎k 𝑝
Note that this bound obviously holds also for 𝑘 ≥ 𝑝.
k𝑁 𝑎 𝑦 k 𝑝
𝑦∈[𝑁] k𝑎 𝑦 k 𝑝 we separate to two cases depending on whether k𝑎k 𝑝 ≥ 𝑁
Í
Now to compute
or not, and then use Claim 4.5.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 16
S IGN - RANK VS . D ISCREPANCY
k𝑁 𝑎 𝑦 k 𝑝
The case k𝑎 k 𝑝 ≥ 𝑁: First, note that in this case we can bound |𝑆 𝑘 | . 𝑁𝑘 . Also to bound k𝑎 𝑦 k 𝑝
,
for 𝑦 ∈ 𝑆 k𝑎 k 𝑝 , we use the bound k𝑁 𝑎 𝑦k 𝑝 ≤ 𝑝. We get
Õ k𝑁 𝑎 𝑦 k 𝑝 Õ 1
≤ 𝑝 .
k𝑎 𝑦k 𝑝 k𝑎 𝑦k 𝑝
𝑦∈[𝑁] 𝑦∈[𝑁]
Í
𝑦∈[𝑁] k𝑎 𝑦 k 𝑝 we use Claim 4.5. Let u ∼ [𝑁] be uniformly chosen, and set the random
1
To compute
variable r to be r = k𝑎uk 𝑝 . Set 𝑔(𝑥) = 𝑥1 . Then we have
1 Õ 1
= 𝔼r 𝑔(r)
𝑁 k𝑎 𝑦k 𝑝
𝑦∈[𝑁]
𝑝−1
Õ
= 𝑔(𝑝) + (𝑔(𝑖) − 𝑔(𝑖 + 1)) Pr[r ≤ 𝑖]
𝑖=1
𝑝−1
Õ
1 1 1 |𝑆 𝑖 |
= + −
𝑝 𝑖 𝑖+1 𝑁
𝑖=1
𝑝−1
1 Õ 1 𝑖
. + ·
𝑝 𝑖 2 𝑁2
𝑖=1
log 𝑝
. .
𝑁2
Overall we get
Õ k𝑁 𝑎 𝑦 k 𝑝 Õ 1 𝑝 log 𝑝
≤ 𝑝 . .
k𝑎 𝑦k 𝑝 k𝑎 𝑦k 𝑝 𝑁
𝑦∈[𝑁] 𝑦∈[𝑁]
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 17
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
The case k𝑎k 𝑝 < 𝑁: Here we use the estimate |𝑆 𝑘 | . k𝑎𝑘k . Also similar to the previous case,
𝑝
k𝑁 𝑎 𝑦k 𝑝 𝑝
we bound k𝑎 𝑦 k ≤ k𝑎 𝑦k . We get
𝑝 𝑝
𝑝−1
1 Õ 1 Õ
= 𝑔(𝑝) + (𝑔(𝑖) − 𝑔(𝑖 + 1)) Pr[r ≤ 𝑖]
𝑁 k𝑎 𝑦k 𝑝
𝑦∈[𝑁] 𝑖=1
𝑝−1
1 Õ 1 1 |𝑆 𝑖 |
= + −
𝑝 𝑖 𝑖+1 𝑁
𝑖=1
𝑝−1
1 Õ 1 𝑖
. + ·
𝑝 𝑖 2 k𝑎 k 𝑝 𝑁
𝑖=1
log 𝑝
. .
k𝑎 k 𝑝 𝑁
So we have
Õ k𝑁 𝑎 𝑦k 𝑝 Õ 1
≤ 𝑝
k𝑎 𝑦k 𝑝 k𝑎 𝑦k 𝑝
𝑦∈[𝑁] 𝑦∈[𝑁]
𝑝 log 𝑝
. .
k𝑎k 𝑝
The lemma follows.
We remark that the following more general statement regarding uniformity of product sets
follows by an argument similar to the proof of Lemma 4.3 which we record here as it may be of
independent interest.
Lemma 4.6. Let 𝑝 ≥ 𝑁 2 be prime, and let 𝐵 ⊆ [𝑁]𝑑 for some positive integer 𝑑. Then
log𝑑 𝑝
!
𝑝𝑑
𝔼x∼[𝑁]𝑑 | 𝔼y∼𝐵 𝜒 𝑎 (hx, yi)| 2 . max k𝑎 k 𝑑𝑝 , · .
k𝑎 k 𝑑𝑝 |𝐵|𝑁 𝑑
References
[1] Noga Alon, Shay Moran, and Amir Yehudayoff: Sign rank versus Vapnik–Chervonenkis
dimension. Sbornik Math., 208(12):1724–1757, 2017. Preliminary version in COLT’16:PMLR.
[doi:10.1070/SM8780] 7
[2] László Babai, Peter Frankl, and Janos Simon: Complexity classes in communica-
tion complexity theory. In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc., 1986.
[doi:10.1109/SFCS.1986.15] 6, 7
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 18
S IGN - RANK VS . D ISCREPANCY
[3] László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom
generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232,
1992. Preliminary version in STOC’89. 2
[4] Ronen Basri, Pedro F. Felzenszwalb, Ross B. Girshick, David W. Jacobs, and Caroline J.
Klivans: Visibility constraints on features of 3D objects. In Proc. Conf. Comp. Vision and Pattern
Recog. (CVPR’09), pp. 1231–1238. IEEE Comp. Soc., 2009. [doi:10.1109/CVPR.2009.5206726]
7
[5] Amey Bhangale and Swastik Kopparty: The complexity of computing the minimum rank
of a sign pattern matrix, 2015. [arXiv:1503.04486] 7
[6] Thomas A. Brown and Joel H. Spencer: Minimization of ±1 matrices under line shifts.
Colloquium Mathematicum, 23:165–171, 1971. [doi:10.4064/cm-23-1-165-171] 2
[7] Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf: On computation and
communication with small bias. In Proc. 22nd IEEE Conf. on Comput. Complexity (CCC’07),
pp. 24–32. IEEE Comp. Soc., 2007. [doi:10.1109/CCC.2007.18] 7
[8] Mark Bun and Justin Thaler: Improved bounds on the sign-rank of AC0 . In Proc. 43rd
Internat. Colloq. on Automata, Languages, and Programming (ICALP’16), pp. 37:1–14. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.37,
ECCC:TR16-075] 2
[9] Arkadev Chattopadhyay and Toniann Pitassi: The story of set disjointness. SIGACT News,
41(3):59–85, 2010. [doi:10.1145/1855118.1855133] 2, 3
[10] Bernard Chazelle: The Discrepancy Method: Randomness and Complexity. Cambridge Univ.
Press, 2000. 2
[11] Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and
probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary
version in FOCS’85. [doi:10.1137/0217015] 2, 6
[12] Johannes G. van der Corput: Verteilungsfunktionen I (Distribution functions, German).
Proc. Akad. Wetenschappen Amsterdam, 38:813–821, 1935. 2
[13] Paul Erdős and Joel H. Spencer: Probabilistic Methods in Combinatorics. Akadémiai Kiadó,
Budapest, and Academic Press, 1971. 2
[14] Jürgen Forster: A linear lower bound on the unbounded error probabilistic communication
complexity. J. Comput. System Sci., 65(4):612–625, 2002. Preliminary version in CCC’01.
[doi:10.1016/S0022-0000(02)00019-3] 4
[15] Anna Gál and Ridwan Syed: Upper bounds on communication in terms of approxi-
mate rank. In Proc. Comp. Sci. Symp. in Russia (CSR’21), pp. 116–130. Springer, 2021.
[doi:10.1007/978-3-030-79416-3_7, ECCC:TR19-006] 7
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 19
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
[16] Hamed Hatami, Kaave Hosseini, and Shachar Lovett: Sign rank vs discrepancy. In Proc.
35th Comput. Complexity Conf. (CCC’20), pp. 18:1–14. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.18, ECCC:TR19-067] 1
[17] Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput.,
37(1):20–46, 2007. Preliminary version in FOCS’01. [doi:10.1137/S0097539702405620] 6
˜
[18] Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2𝑂(𝑛 ) . J. Comput. System
1/3
Sci., 68(2):303–318, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.007] 2
[19] Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman: Complexity
measures of sign matrices. Combinatorica, 27(4):439–463, 2007. [doi:10.1007/s00493-007-
2160-5] 2, 5
[20] Nati Linial and Adi Shraibman: Learning complexity vs. communication complex-
ity. Combin. Probab. Comput., 18(1–2):227–245, 2009. Preliminary version in CCC’08.
[doi:10.1017/S0963548308009656] 2, 4
[21] Noam Nisan: The communication complexity of threshold gates. In D. Miklós, T. Szőnyi,
and V. T. Sós, editors, Combinatorics, Paul Erdős is Eighty, volume 1, pp. 301–315. Bolyai
Society, Budapest and North-Holland, 1993. Author’s website. 3, 11
[22] Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput.
System Sci., 33(1):106–123, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-
0000(86)90046-2] 2, 6
[23] Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of A𝐶 0 . SIAM J.
Comput., 39(5):1833–1855, 2010. Preliminary version in FOCS’08. [doi:10.1137/080744037,
ECCC:TR08-016] 2
[24] Alexander A. Sherstov: Halfspace matrices. Comput. Complexity, 17(2):149–178, 2008.
Preliminary version in CCC’07. [doi:10.1007/s00037-008-0242-4] 7
[25] Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000,
2011. [doi:10.1137/080733644, arXiv:0906.4291] 7
[26] Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two
halfspaces by polynomials. Combinatorica, 33(1):73–96, 2013. Preliminary version in STOC’10.
[doi:10.1007/s00493-013-2759-7, arXiv:0910.4224, ECCC:TR10-025] 7
[27] Alexander A. Sherstov: The hardest halfspace. Comput. Complexity, 30(2):11, 2021.
[doi:10.1007/s00037-021-00211-4, arXiv:1902.01765, ECCC:TR19-016] 3, 7
[28] Justin Thaler: Lower bounds for the approximate degree of block-composed func-
tions. In Proc. 43rd Internat. Colloq. on Automata, Languages, and Programming
(ICALP’16), pp. 17:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.
[doi:10.4230/LIPIcs.ICALP.2016.17, ECCC:TR14-150] 7
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 20
S IGN - RANK VS . D ISCREPANCY
[29] Hugh E. Warren: Lower bounds for approximation by nonlinear manifolds. Trans. AMS,
133(1):167–178, 1968. [doi:10.1090/S0002-9947-1968-0226281-1] 2
AUTHORS
Hamed Hatami
Associate professor
Department of Computer Science
McGill University
Montreal, Quebec, Canada
hatami cs mcgill edu
https://www.cs.mcgill.ca/~hatami/
Kaave Hosseini
Assistant professor
Department of Computer Science
University of Rochester
Rochester, New York, USA
kaave hosseini rochester edu
https://www.cs.rochester.edu/u/shossei2/
Shachar Lovett
Associate professor
Department of Computer Science
University of California San Diego
San Diego, California, USA
slovett ucsd edu
https://cseweb.ucsd.edu/~slovett/home.html
ABOUT THE AUTHORS
Hamed Hatami received his Ph. D. from the Department of Computer Science at
the University of Toronto in 2009 under Michael Molloy and Balázs Szegedy.
Afterward, he became a Veblen fellow at the Institute for Advanced Study and
the Department of Mathematics at Princeton University until 2010. Since 2010 he
has been on the faculty at the School of Computer Science at McGill University.
His research focuses on the applications of mathematical analysis to theoretical
computer science and combinatorics.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 21
H AMED H ATAMI , K AAVE H OSSEINI , AND S HACHAR L OVETT
Kaave Hosseini received his Ph. D. from the Department of Computer Science and
Engineering at University of California, San Diego in 2019 under the supervision
of Shachar Lovett. Then he was a postdoctoral associate in the Department of
Mathematical Sciences at Carnegie Mellon University until 2021. Since 2021,
he has been on the faculty in the Department of Computer Science at the
University of Rochester. His research interests are in additive combinatorics,
pseudo-randomness, and their applications in algorithms and computational
complexity.
Shachar Lovett received his Ph. D. from the Weizmann Institute of Science in 2010
under the supervision of Omer Reingold and Ran Raz. He was a postdoctoral
researcher at the Institute for Advanced Study until 2012. Since 2012, he has been
on the faculty at the University of California, San Diego. He is a recipient of an
NSF CAREER award and a Sloan fellowship. His research is broadly in theoretical
computer science and combinatorics. In particular: computational complexity,
randomness and pseudo-randomness, algebraic constructions, coding theory,
additive combinatorics and combinatorial aspects of high-dimensional geometry.
He is happily married and has four kids.
T HEORY OF C OMPUTING, Volume 18 (19), 2022, pp. 1–22 22