Statistical Algorithms and a Lower Bound for Detecting Planted
Cliques

arXiv:1201.1214v6 [cs.CC] 15 Aug 2016

Vitaly Feldman∗

Elena Grigorescu†‡

Santosh S. Vempala¶‡

Lev Reyzin§‡

Ying Xiao¶‡

Abstract
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle.
For such algorithms, access to the input distribution is limited to obtaining an estimate of
the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and
in practice, e.g., moments-based methods, local search, standard iterative methods for convex
optimization, MCMC and simulated annealing can be implemented in this framework. Our
framework is based on, and generalizes, the statistical query model in learning theory [Kearns,
1998].
Our main application is a nearly optimal lower bound on the complexity of any statistical
query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph
distributions) when the planted clique has size O(n1/2−δ ) for any constant δ > 0. The assumed
hardness of variants of these problems has been used to prove hardness of several other problems
and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete
evidence of hardness, thus supporting these assumptions.

∗

IBM Almaden Research Center.
Department of Computer Science, Purdue University. Supported by the National Science Foundation under
Grant #1019343 to the Computing Research Association for the CIFellows Project.
‡
Research supported in part by NSF awards CCF-0915903 and CCF-1217793.
§
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. Research
supported by a Simons Postdoctoral Fellowship.
¶
School of Computer Science, Georgia Institute of Technology. Research supported by NSF awards CCF-1217793
and EAGER-1415498.
†

Contents
1 Introduction

2

2 Definitions and Overview
2.1 Problems over Distributions . . . . . . . . . .
2.2 Statistical Algorithms . . . . . . . . . . . . .
2.3 Statistical Dimension . . . . . . . . . . . . . .
2.4 Applications to the Planted Biclique Problem
2.5 Subsequent Work . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

5
5
6
7
10
12

3 Lower Bounds from Statistical Dimension
3.1 Lower Bounds for Statistical Query Algorithms . . .
3.1.1 Decision Problems . . . . . . . . . . . . . . .
3.2 Statistical Dimension Based on Pairwise Correlations
3.3 Lower Bounds for 1-bit Sampling Algorithms . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

13
13
16
16
18

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4 Warm-up: MAX-XOR-SAT

22

5 Planted Biclique and Densest Subgraph
23
5.1 Statistical Dimension of Planted Biclique . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Generalized Planted Densest Subgraph . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Applications to Statistical Query Learning
30
6.1 Relationship to SQ-DIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2 Lower Bounds for 1-bit Sampling Oracle . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.3 New Lower Bound for Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
A Average-case vs Distributional Planted Bipartite Clique

1

38

1

Introduction

We study the complexity of problems where the input consists of independent samples from an
unknown distribution. Such problems are at the heart of machine learning and statistics (and their
numerous applications) and also occur in many other contexts such as compressed sensing and
cryptography. While several methods have been developed to estimate the sample complexity of
such problems (e.g. VC dimension [Vapnik and Chervonenkis, 1971] and Rademacher complexity
[Bartlett and Mendelson, 2002]), proving lower bounds on the computational complexity of these
problems has been much more challenging. The traditional approach to proving lower bounds is via
reductions and by finding distributions that can generate instances of some problem conjectured
to be intractable (e.g., assuming NP 6= RP).
Here we present a different approach. We show that algorithms which access the unknown distribution only via a statistical query (SQ) oracle have high complexity, unconditionally. Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented
using only access to such an oracle; these include Expectation Maximization (EM) [Dempster et al.,
1977], local search, MCMC optimization [Tanner and Wong, 1987, Gelfand and Smith, 1990], simulated annealing [Kirkpatrick et al., 1983, Černý, 1985], first and second order methods for linear/convex optimization, [Dunagan and Vempala, 2008, Belloni et al., 2009], k-means, Principal
Component Analysis (PCA), Independent Component Analysis (ICA), Naı̈ve Bayes, Neural Networks and many others (see [Chu et al., 2006] and [Blum et al., 2005] for proofs and many other
examples). In fact, we are aware of only one algorithm that provably does not have a statistical
query counterpart: Gaussian elimination for solving linear equations over a field (e.g. mod 2).
Informally, a statistical query oracle provides an estimate of the expected value of any given
bounded real-valued function within some tolerance. Many popular algorithms rely only on the
average value of various functions over random samples (commonly referred to as empirical averages). Standard Chernoff-Hoeffding bounds imply that the average value of a bounded function
on the independent samples will be highly concentrated around the expectation on the unknown
distribution (and, indeed in many cases the empirical average is used precisely to obtain an estimate of the expectation). As a result such algorithms can often be equivalently analyzed in our
oracle-based model.
Our approach also allows proving lower bounds against algorithms that rely on a 1-bit sampling
oracle, referred to as 1-bit sampling algorithms. This oracle provides the value of any Boolean
function on a fresh random sample from the distribution. Many existing algorithms require only
such limited access to random samples. Others can be implemented using such access to samples
(possibly using a polynomially larger number of samples). For brevity, we refer to algorithms that
rely on either of these types of oracles as statistical algorithms.
For example, many problems over distributions are solved using convex programs. Such a
problem is typically formulated as finding an approximation to minz∈K Ex∼D [f (x, z)] for some
convex set K and functions f (x, ·) that are convex in the second parameter z. A standard approach
(both in theory and practice) to solve such a problem is to use a gradient descent-based technique.
The gradient of the objective function is
∇z E[f (x, z)] = E[∇z f (x, z)]
x

x

and is usually estimated using the average value of ∇z f (x, z) on (some of) the given random samples.
However, standard analysis of gradient descent-based algorithms implies that a sufficiently accurate
2

estimate of each of the coordinates of Ex [∇z f (x, z)] would also suffice. Hence, for an objective
function of the form above, gradient descent can be implemented using either of the above oracles
(detailed analysis of such implementations can be found in a subsequent work [Feldman et al.,
2015]).
The key motivation for our framework is the empirical observation that almost all algorithms
that work on random samples are either already statistical in our sense or have natural statistical counterparts. Thus, lower bounds for statistical algorithms can be directly translated into
lower bounds against a large number of existing approaches. We present the formal oracle-based
definitions of statistical algorithms in Section 2.
Our model is based on the statistical query learning model [Kearns, 1998] defined as a restriction
of Valiant’s [1984] PAC learning model. The primary goal of the restriction was to simplify the
design of noise-tolerant learning algorithms. As was shown by Kearns and others in subsequent
works, almost all classes of functions that can be learned efficiently can also be efficiently learned in
the SQ model. A notable and so far unique exception is the algorithm for learning parities, based
on Gaussian elimination. As was already shown by Kearns [1998], parities require exponentially
many queries to learn in the SQ model. Further, Blum et al. [1994] proved that the number of
SQs required for weak learning (that is, for obtaining a non-negligible advantage over the random
guessing) of a class of functions C over a fixed distribution D is characterized by a combinatorial
parameter of C and D, referred to as SQ-DIM(C, D), the SQ dimension.
We consider SQ algorithms in the broader context of arbitrary computational problems over
distributions. We also define an SQ oracle that strengthens the oracle introduced by Kearns [1998].
For any problem over distributions we define a parameter of the problem that lower bounds the
complexity of solving the problem by any SQ algorithm in the same way that SQ-DIM lower bounds
the complexity of learning in the SQ model. Our techniques for proving lower bounds are also based
on methods developed for lower-bounding the complexity of SQ learning algorithms. However, as
we will describe later, they depart from the known techniques in a number of significant ways that
are necessary for our more general setting and our applications.
The 1-bit sampling oracle and its more general k-bit version was introduced by Ben-David and Dichterman
[1998]. They showed that it is equivalent (up to polynomial factors) to the SQ oracle. Using our
stronger SQ oracle we sharpen this equivalence. This sharper relationship is crucial for obtaining
meaningful lower bounds against 1-bit sampling algorithms in our applications.
We demonstrate our techniques by applying them to the problems of detecting planted bipartite
cliques and planted bipartite dense subgraphs. We now define these problems precisely and give
some background.
Detecting Planted Cliques. In the planted clique problem, we are given a graph G whose edges
are generated by starting with a random graph Gn,1/2 , then “planting,” i.e., adding edges to form
a clique on k randomly chosen vertices. Jerrum [1992] and Kucera [1995] introduced the planted
clique problem as a potentially easier variant of the classical problem of finding the largest clique
in a random graph [Karp, 1979]. A random graph Gn,1/2 contains a clique of size 2 log n with
high probability, and a simple greedy algorithm can find one of size log n. Finding cliques of size
(2−ǫ) log n is a hard problem for any ǫ > 0. Planting a larger clique should make it easier to find one.
The problem of finding the smallest k for which the
√ planted clique can be detected in polynomial
time has attracted significant attention. For k ≥ c n log n, simply picking vertices of large degrees
√
suffices [Kucera, 1995]. Cliques of size k = Ω( n) can be found using spectral methods [Alon et al.,
1998, McSherry, 2001, Coja-Oghlan, 2010], via SDPs [Feige and Krauthgamer, 2000], combinatorial
3

methods [Feige and Ron, 2010, Dekel et al., 2011], nuclear norm minimization [Ames and Vavasis,
2011] and belief propagation [Deshpande and Montanari, 2013].
While there is no known polynomial-time algorithm that can detect cliques of size below the
√
threshold of Ω( n), there is a quasipolynomial algorithm for any k ≥ 2 log n: enumerate subsets
of size 2 log n; for each subset that forms a clique, take all common neighbors of the subset; one of
these will be the planted clique. This is also the fastest known algorithm for any k = O(n1/2−δ ),
where δ > 0.
Some evidence of the hardness of the problem was shown by Jerrum [1992] who proved that
√
a specific approach using a Markov chain cannot be efficient for k = o( n). Additional evidence of hardness is given in [Feige and Krauthgamer, 2003], where it is shown that LovászSchrijver SDP relaxations, which include the SDP used in [Feige and Krauthgamer, 2000], can√
not be used to efficiently find cliques of size k = o( n). Most recently, lower bounds against
a constant level of the more powerful Sum-of-Squares SDP hierarchy were shown by Meka et al.
[2015] and Deshpande and Montanari [2015]. The problem has been used to generate cryptographic
primitives [Juels and Peinado, 2000], and as a hardness assumption in a large number of works
(e.g. [Alon et al., 2007, Hazan and Krauthgamer, 2011, Minder and Vilenchik, 2009, Berthet and Rigollet,
2013, Dughmi, 2014]).
We focus on the bipartite planted clique problem, where a (k × k)-biclique is planted in a
random bipartite graph. A densest-subgraph version of the bipartite planted clique problem has
been used as a hard problem for cryptographic applications [Applebaum et al., 2010]. The bipartite
version can be easily seen to be at least as hard as the original version. At the same time all
known bounds and algorithms for the k-clique problem can be easily adapted to the bipartite case
(e.g. [Ames and Vavasis, 2011]). Therefore it is natural to expect that new upper bounds on the
planted k-clique problem would also yield new upper bounds for the bipartite case.
The starting point of our investigation for this problem is the property of the planted k-biclique
problem that it has an equivalent formulation as a problem over distributions defined as follows.
Problem 1.1. Fix an integer k, 1 ≤ k ≤ n, and a subset of k indices S ⊆ {1, 2, . . . , n}. The
input distribution DS on vectors x ∈ {0, 1}n is defined as follows: with probability 1 − (k/n), x is
uniform over {0, 1}n ; and with probability k/n, x is such that its k coordinates from S are set to 1,
and the remaining coordinates are uniform in {0, 1}. For an integer t, the distributional planted
k-biclique problem with t samples is the problem of finding the unknown subset S using t samples
drawn randomly from DS .
One can view samples x1 , . . . , xt as adjacency vectors of the vertices of a bipartite graph as
follows: the bipartite graph has n vertices on the right (with k marked as members of the clique)
and t vertices on the left. Each of the t samples gives the adjacency vector of the corresponding
vertex on the left. It is not hard to see that for t = n, conditioned on the event of getting exactly k
samples with planted indices, we will get a random bipartite graph with a planted (k × k)-biclique
(we prove the equivalence formally in Appendix A).
One interesting approach for finding the planted clique was proposed by Frieze and Kannan
[2008]. They gave a reduction from finding a planted clique in a random graph to finding a direction that maximizes a 2nd order tensor norm; this was extended to general r’th order tensor norm
in [Brubaker and Vempala, 2009].Specifically, they show that maximizing the r’th moment (or the
2-norm of an r’th order tensor) allows one to recover planted cliques of size Ω̃(n1/r ). A related
approach is to maximize the 3rd or higher moment of the distribution given by the distributional
4

planted clique problem. For this approach it is natural to consider the following type of optimization algorithm: start with some unit vector u, then estimate the gradient at u (via samples), move
along that direction and return to the sphere; repeat to reach an approximate local maximum. Unfortunately, over the unit sphere, the expected r’th moment function can have (exponentially) many
local maxima even for simple distributions. A more sophisticated approach [Kannan] is through
Markov chains or simulated annealing; it attempts to sample unit vectors from a distribution on
the sphere which is heavier on vectors that induce a higher moment, e.g., u is sampled with density
proportional to ef (u) where f (u) is the expected r’th moment along u. This could be implemented
by a Markov chain with a Metropolis filter [Metropolis et al., 1953, Hastings, 1970] ensuring a proportional steady state distribution. If the Markov chain were to mix rapidly, that would give an
efficient approximation algorithm because sampling from the steady state likely gives a vector of
high moment. At each step, all one needs is to be able to estimate f (u), which can be done by
sampling from the input distribution.
As we will see presently, these approaches can be easily implemented in our framework and
will have provably high complexity. For the distributional planted biclique problem, SQ algorithms
1
need nΩ(log n) queries to detect planted bicliques of size k < n 2 −δ for any δ > 0. Even stronger
exponential bounds apply for the more general problem of detecting planted dense subgraphs of
the same size. These bounds match the known upper bounds. To describe these results precisely
and discuss exactly what they mean for the complexity of these problems, we will need to define
the models of statistical algorithms, the complexity measures we use, and our main tool for proving
lower bounds, a notion of statistical dimension of a set of distributions. We do this in the next
section. In Section 3 we prove our general lower bound results and in Section 5 we estimate the
statistical dimension of detecting planted bicliques and dense subgraphs.

2

Definitions and Overview

Here we formally define statistical algorithms and the key notion of statistical dimension, and then
describe the resulting lower bounds in detail.

2.1

Problems over Distributions

We begin by formally defining the class of problems addressed by our framework.
Definition 2.1 (Search problems over distributions). For a domain X, let D be a set of distributions over X, let F be a set called solutions and Z : D → 2F be a map from a distribution D ∈ D
to a subset of solutions Z(D) ⊆ F that are defined to be valid solutions for D. The distributional
search problem Z over D and F using t samples is to find a valid solution f ∈ Z(D) given access
(to an oracle or samples from) an unknown D ∈ D.
In some settings it is natural to parameterize the set of valid solutions by additional parameters,
such as accuracy. The extension of the definition to such settings is immediate. An example of
a distributional search problem is the distributional planted k-biclique we described in Definition
1.1. In this case the domain X is {0, 1}n , the set of input distributions is all the distributions with
a planted k-biclique D = {DS | S ⊂ [n], |S| = k} and the set of solutions is the set of all subsets
of size k: F = {S | S ⊂ [n], |S| = k}. For each DS there is a single valid solution S. For a second
example, we point the reader to the distributional MAX-XOR-SAT problem in Section 4.
5

We note that this definition also captures decision problems by having F = {0, 1}. A simple
example of a decision problem over distributions that is relevant to our discussion is that of distinguishing a planted biclique distribution from the uniform distribution over {0, 1}n which we denote
by U . Here the set of input distributions is D = {U } ∪ {DS | S ⊂ [n], |S| = k}. The only valid
solution for a planted biclique distribution DS is 1 and the only valid solution for U is 0. For a
solution f ∈ F, we denote by Zf the set of distributions in D for which f is a valid solution.
It is important to note that the number of available random samples t can have a major influence on the complexity of the problem. First, for most problems there is a minimum t for which
the problem is information-theoretically solvable. This value is often referred to as the sample complexity of the problem. But even for t which is larger than the sample complexity of the problem,
having more samples can make the problem easier computationally. For example, in the context
of attribute-efficient learning, there is a problem that is intractable with few samples (under cryptographic assumptions) but is easy to solve with a larger (but still polynomial) number of samples
[Servedio, 2000]. Our distributional planted biclique problem exhibits the same phenomenon.

2.2

Statistical Algorithms

The statistical query learning model of Kearns [1998] is a restriction of the PAC model [Valiant,
1984]. It introduces an oracle that allows a learning algorithm to obtain an estimate of the expectation of any bounded function of an example. A query to such an oracle is referred to as
statistical query. Kearns showed that many known PAC learning algorithms can be expressed
as algorithms using statistical queries instead of random examples themselves. The main goal of
Kearns’ model was to give a simple way to design algorithms tolerant to random classification
noise. Since the introduction of the model SQ algorithms have been given for many more learning
tasks and the model itself found applications in a number of other contexts such as differential privacy [Blum et al., 2005, Kasiviswanathan et al., 2011], learning on massively parallel architectures
[Chu et al., 2006] and evolvability [Feldman, 2008].
In the same spirit, for general search problems over a distribution, we define SQ algorithms as
algorithms that do not see samples from the distribution but instead have access to a SQ oracle.
The first SQ oracle we define is the natural generalization of the oracle defined by Kearns [1998] to
samples from an arbitrary distribution.
Definition 2.2 (STAT oracle). Let D be the input distribution over the domain X. For a tolerance
parameter τ > 0, STAT(τ ) oracle is the oracle that for any query function h : X → [−1, 1], returns
a value


v∈

E [h(x)] − τ, E [h(x)] + τ .
x∼D

x∼D

The general algorithmic techniques mentioned earlier can all be expressed as algorithms using
STAT oracle instead of samples themselves, in most cases in a straightforward way. We would
also like to note that in the PAC learning model some of the algorithms, such as the Perceptron
algorithm, did not initially appear to fall into the SQ framework but SQ analogues were later found
for all known learning techniques except Gaussian elimination (for specific examples, see [Kearns,
1998] and [Blum et al., 1998]). We expect the situation to be similar even in the broader context
of search problems over distributions.
The most natural realization of STAT(τ ) oracle is one that computes h on O(1/τ 2 ) random
samples from D and returns their average. Chernoff’s bound implies that the estimate is within
6

the desired tolerance (with constant probability). However, if h(x) is very biased (e.g. equal to 0
with high probability), it can be estimated with fewer samples. Our primary application requires a
tight bound on the number of samples necessary to solve a problem over distributions. Therefore we
define a stronger version of STAT oracle which tightly captures the accuracy of an estimate of the
expectation given by random samples. More formally, for a Boolean query function h : X → {0, 1},
VSTAT(t) can return any value v for which the Binomial distribution B(t, v) (sum of t independent
Bernoulli variables with bias v) is statistically close (for some constant distance) to B(t, E[h]). See
Sec. 3.3 for more details on this correspondence.
Definition 2.3 (VSTAT oracle). Let D be the input distribution over the domain X. For a sample
size parameter t > 0, VSTAT(t) oracle is the oracle that for any query
h : X → [0, 1],

 function
q
.
returns a value v ∈ [p − τ, p + τ ] , where p = Ex∼D [h(x)] and τ = max 1t , p(1−p)
t

√
Note that VSTAT(t) √
always returns the value of the expectation within 1/ t. Therefore it is
no weaker than STAT(1/ t) and no stronger than STAT(1/t).
The STAT and VSTAT oracles we defined can return any value within the given tolerance and
therefore can make adversarial choices. We also aim to prove lower bounds against algorithms
that use a more benign, 1-bit sampling oracle1 . The 1-bit sampling oracle gives the algorithm
the true value of a Boolean query function on a randomly chosen sample. This oracle is a special
case of the k-bit sampling oracle introduced by Ben-David and Dichterman [1998] who refer to it
as the weak Restricted Focus of Attention (wRFA) model and is also equivalent to the Honest SQ
oracle of Yang [2001]. Learning in this model has been studied in more recent work motivated by
communication constraints on data processing in a distributed computing system. [Zhang et al.,
2013, Steinhardt and Duchi, 2015, Steinhardt et al., 2016].

Definition 2.4 (1-STAT oracle). Let D be the input distribution over the domain X. The 1-STAT
oracle is the oracle that given any function h : X → {0, 1}, takes an independent random sample x
from D and returns h(x).
Note that the 1-STAT oracle draws a fresh sample upon each time it is called. Without resampling each time, the answers of the 1-STAT oracle could be easily used to recover any sample
bit-by-bit, making it equivalent to having access to random samples. Note that the 1-STAT oracle
can be used to simulate VSTAT (with high probability) by taking the average of O(t) replies of
1-STAT for the same function h. While it might seem that access to 1-STAT gives an algorithm
more power than access to VSTAT we will show that t samples from 1-STAT can be simulated
using access to VSTAT(O(t)). This will allow us to translate our lower bounds on SQ algorithms
with access to VSTAT to lower bounds against 1-bit sampling algorithms.

2.3

Statistical Dimension

The main tool in our analysis is an information-theoretic bound on the complexity of statistical
algorithms. Our definitions originate from the statistical query (SQ) dimension [Blum et al., 1994]
used to characterize SQ learning algorithms. Roughly speaking, the SQ dimension corresponds to
the number of nearly uncorrelated labeling functions in a class (see Section 6.1 for the details of
the definition and the relationship to our bounds).
1

In the STOC 2013 extended abstract, this oracle is also called the unbiased statistical oracle

7

We introduce a natural generalization and strengthening of this approach to search problems
over arbitrary sets of distributions and prove lower bounds on the complexity of statistical algorithms based on the generalized notion. Our definition departs from SQ dimension in three aspects.
(1) Our notion applies to any set of distributions; in the learning setting all known definitions of
statistical dimension require fixing the distribution over the domain and only allow varying the
labeling function. Such an extension was not known even in the context of PAC learning. (2)
Instead of relying on a bound on pairwise correlations, our dimension relies on a bound on average
correlations in a large set of distributions. This weaker condition allows us to derive tight bounds
on the complexity of SQ algorithms for the planted k-biclique problem. (3) We show that our
notion of dimension also gives lower bounds for the stronger VSTAT oracle (without incurring a
quadratic loss in the parameter).
We now define our dimension formally. For two functions f, g : X → R and a distribution D
with probability density function D(x), the inner product of f and g over D is defined as
.
hf, giD = E [f (x)g(x)].
x∼D

p
The norm of f over D is kf kD = hf, f iD . We remark that, by convention, the integral from the
inner product is taken only over the support of D, i.e. for x ∈ X such that D(x) 6= 0. Given a
distribution D over X let D(x) denote the probability density function of D relative to some fixed
underlying measure over X (for example uniform distribution for discrete X or Lebesgue measure
over Rn ). Our bound is based on the inner products between functions of the following form:
(D ′ (x) − D(x))/D(x) where D ′ and D are distributions over X. For this to be well-defined, we will
only consider cases where D(x) = 0 implies D ′ (x) = 0, in which case D ′ (x)/D(x) is treated as 1.
To see why such functions are relevant to our discussion, note that for every real-valued function
f over X,
 ′


 ′
D −D
D (x)
[f
(x)]
=
f
(x)
−
,
f
.
[f
(x)]
=
[f
(x)]
−
E
E
E
E
D
x∼D
x∼D D(x)
x∼D
x∼D ′
D
This means that the inner product of any function f with (D ′ − D)/D is equal to the difference
of expectations of f under the two distributions. Analyzing this quantity for an arbitrary set of
functions f was the high-level approach of statistical query lower bounds for learning. Here we
depart from this approach, by defining a pairwise correlation of two distributions, independent of
any specific query function. For two distributions D1 , D2 and a reference distribution D, their
pairwise correlation is defined as:


D1
D2
χD (D1 , D2 ) =
.
− 1,
−1
D
D
D
When D1 = D2 , the quantity h DD1 − 1, DD1 − 1iD is known as the χ2 (D1 , D) distance and is widely
used for hypothesis testing in statistics [Pearson, 1900].
A key notion for our statistical dimension is the average correlation of a set of distributions D ′
relative to a distribution D. We denote it by ρ(D ′ , D) and define as follows:


X
X
D2
1
D1
. 1
′
ρ(D , D) = ′ 2
.
− 1,
−1
χD (D1 , D2 ) = ′ 2
|D |
|D |
D
D
D
′
′
D1 ,D2 ∈D

D1 ,D2 ∈D

8

Bounds on pairwise correlations easily imply bounds on the average correlation (see Lemma
3.10 for a proof). In Section 3.2 we describe a pairwise-correlation version of our bounds. It is
sufficient for some applications and generalizes the statistical query dimension from learning theory
(see Section 6.1 for the details). However, to obtain our nearly tight lower bounds for planted
biclique, we will need to bound the average pairwise correlation directly, and with significantly
better bounds than what is possible from pairwise correlations alone.
We are now ready to define the concept of statistical dimension. We first define the statistical
dimension with average correlation of a set of distributions relative to some reference distribution.
It captures the complexity of distinguishing distributions in D from D.
Definition 2.5. For γ̄ > 0, domain X, a set of distributions D over X and a reference distribution
D over X the statistical dimension of D relative to D with average correlation γ̄ is defined to be
the largest value d such that for any subset D ′ ⊆ D, where |D ′ | ≥ |D|/d, ρ(D ′ , D) ≤ γ̄. We denote
it by SDA(D, D, γ̄).
Intuitively, the definition says that any 1/d fraction of the set of distributions has low pairwise
correlation; the largest such d is the statistical dimension.
For general search problems over distributions we define the statistical dimension by reducing it
to the statistical dimension of some set of input distributions relative to some reference distribution.
Definition 2.6. For γ̄ > 0, domain X, a search problem Z over a set of solutions F and a class
of distributions D over X, let d be the largest value such that there exists a reference distribution
D over X and a finite set of distributions DD ⊆ D with the following property: for any solution
f ∈ F the set Df = DD \ Zf is non-empty and SDA(Df , D, γ̄) ≥ d. We define the statistical
dimension with average correlation γ̄ of Z to be d and denote it by SDA(Z, γ̄).
The statistical dimension with average correlation γ̄ of a search problem over distributions gives
a lower bound on the complexity of any deterministic statistical algorithm for the problem that
uses queries to VSTAT(1/(3γ̄)).
Theorem 2.7. Let X be a domain and Z be a search problem over a set of solutions F and a class
of distributions D over X. For γ̄ > 0 let d = SDA(Z, γ̄). Any SQ algorithm requires at least d calls
to VSTAT(1/(3γ̄)) oracle to solve Z.
In Section 3.1 we give a refinement of SDA, by introducing a parameter which additionally
bounds the size of the set Df (and not just that it is non-empty). This refined notion allows
us to extend the lower bound to randomized SQ algorithms. In Section 3.3 we use this refined
notion of SDA to also show that (with high probability) one can simulate t samples of 1-STAT
using VSTAT(O(t)). This implies that lower bounds on SDA imply lower bounds on the number
of queries required by any 1-bit sampling algorithm (Theorem 3.17).
In Section 6 we show that our bounds generalize and strengthen the known results for SQ
learning that are based on SQ-DIM [Blum et al., 1994, Yang, 2005]. In the statement below, the
statistical dimension SDA(C, D ′ , γ̄) uses the average pairwise correlation of Boolean functions from
a set C relative to a distribution D ′ over a domain X ′ , that is hf1 , f2 iD′ , where f1 , f2 ∈ C (rather
than distributions as in the definitions above). It is formally defined in Section 6 and is always at
least as large as the statistical query dimension used in earlier work in learning theory.
Theorem 2.8. Let C be a set of Boolean functions, D ′ be a distribution over X ′ and let d =
SDA(C, D ′ , γ̄) for some γ̄ > 0.pThen any SQ algorithm that, with probability at least 2/3, learns C
over D ′ with error ǫ < 1/2 − 1/(3γ̄) requires at least d/3 − 1 queries to VSTAT(1/(3γ̄)).
9

At a high level, our proof works as follows. The first step of the proof is a reduction from a
decision problem in which the algorithm only needs to distinguish all the distributions in the set
DD (except those in Zf for some f ) from the reference distribution D. To distinguish between
distributions the algorithm needs to ask a query g such that ED [g] cannot be used as a response of
VSTAT(1/(3γ̄)) for D ′ ∈ Df . In the key component of the proof we show that if a query function
g to VSTAT(1/(3γ̄)) distinguishes between a distribution D and any distribution D ′ ∈ D ′ , then D ′
must have average correlation of at least γ̄ relative to D. The condition that for any |D ′ | ≥ |Df |/d,
ρ(D ′ , D) < γ̄ then immediately implies that at least d queries are required to distinguish any
distribution in Df from D. We remark that an immediate corollary of this proof technique is that
the decision problem in which the algorithm needs to decide whether the input distribution is in Df
or is equal to the reference distribution D also has statistical dimension at least d. We elaborate
on this in Theorem 3.7 where we give a simplified version of our lower bound for decision problems
of this type.

2.4

Applications to the Planted Biclique Problem

We prove the following lower bound for the distributional planted biclique problem.
Theorem 2.9. For any constant δ > 0, any k ≤ n1/2−δ and r > 0, at least nΩ(log r) queries to
VSTAT(n2 /(rk 2 )) are required to solve the distributional planted k-biclique with probability at least
2/3. In particular, no polynomial-time statistical algorithm can solve the problem using queries
to VSTAT(o(n2 /k2 )) and any SQ algorithm requires nΩ(log n) queries to VSTAT(n2−δ /k2 ). This
lower bound also applies to the problem of distinguishing any planted k-biclique distribution from
the uniform distribution over {0, 1}n (no planting).
This bound is essentially tight. For every index in the planted set S, the probability that the
corresponding bit of a randomly chosen point is set to 1 is 1/2 + k/(2n), whereas for every index
not in S, this probability is 1/2. Therefore using n queries to VSTAT(16n2 /k2 ) (i.e., of tolerance
k/4n) it is easy to recover S. Indeed, this can be done by using the query functions hi (x) = xi , for
each i ∈ [n]. So, the answers of the VSTAT oracle represent the expected value of the ith bit over
the sample.
There is also a SQ algorithm that uses nO(log n) queries to VSTAT(25n/k) (corresponding to a
significantly smaller number of samples) to find the planted set for any k ≥ log n. In fact, the same
algorithm can be used for the standard planted clique problem that achieves complexity nO(log n) .
We enumerate over subsets T ⊆ [n] of log n indices and query VSTAT(25n/k) with the function
gT : {0, 1}n → {0, 1} defined as 1 if and only if the point has ones in all coordinates in T . Therefore,
if the set T is included in the planted set then




k
k k+1
k
− log n
,
2
∈
.
E[gT ] = · 1 + 1 −
n
n
n
n
D
p
With this expectation, VSTAT(25n/k) has tolerance at most k(k + 1)/25n2 ≤ (k + 1)/5n and
will return at least k/n − (k + 1)/(5n) > 3k/(4n). If, on the other hand, at least one element of T
is not from the planted set, then ED [gT ] ≤ k/(2n) + 1/n and VSTAT(25n/k) will return at most
(k + 2)/(2n) + (k + 2)/(5n) < 3k/(4n). Thus, we will know all (log n)-sized subsets of the planted
set and hence the entire planted set. We remark that this algorithm demonstrates the difference
between STAT and VSTAT oracles. Implementing this algorithm using the STAT oracle would
10

require tolerance of Ω(k/n) which corresponds to O(n2 /k2 ) samples. This is the same tolerance as
the polynomial-time degree-based algorithm needs (estimate degree of each vertex), so one cannot
hope to have a superpolynomial lower bound against STAT(k/n).
To summarize, n samples directly correspond to having access to VSTAT(O(n)). The discussion
above shows that the distributional planted biclique problem can be solved in polynomial time when
√
k = Ω( n). At the same time, Theorem 2.9 implies that for k ≤ n1/2−δ , any SQ algorithm will
require nΩ(log n) queries to VSTAT(n1+δ ).
We now turn to stating our bounds for 1-bit sampling algorithms.
Theorem 2.10. For any constant δ > 0 and any k ≤ n1/2−δ , any 1-bit sampling algorithm that with
probability at least 2/3 can distinguish between the uniform distribution and any planted k-biclique
distribution requires Ω(n2 /k2 ) queries to 1-STAT.
Each query of a 1-bit sampling algorithm uses a new sample from D. Therefore this bound
implies that any algorithm that does not reuse samples will require Ω(n2 /k2 ) samples. To place
this bound in context, we note that it is easy to detect whether a biclique of size k has been planted
using Õ(n2 /k2 ) samples (as before, to detect if a coordinate i is in the planted set we can compute
the average of xi on Õ(n2 /k2 ) samples). Of course, finding all coordinates in the set would require
reusing samples (which 1-bit sampling algorithms cannot do). Note that n2 /k2 ≤ n if and only if
√
k ≥ n.
A closely related problem is the planted densest subgraph problem, where edges in the planted
subset appear with higher probability than in the remaining graph. This is a variant of the densest
k-subgraph problem, which itself is a natural generalization of k-clique that asks to recover the
densest k-vertex subgraph of a given n-vertex graph [Feige, 2002, Khot, 2004, Bhaskara et al.,
2010, 2012]. The conjectured hardness of its average case variant, the planted densest subgraph
problem, has been used in public key encryption schemes [Applebaum et al., 2010] and in analyzing
parameters specific to financial markets [Arora et al., 2010]. We define the following distributional
version of this problem:
Problem 2.11. Fix 0 < q < p ≤ 1. For 1 ≤ k ≤ n, let S ⊆ [n] be a set of k vertex indices and DS
be a distribution over {0, 1}n such that when x ∼ DS , with probability 1 − (k/n) the entries of x
are independently q-biased Bernoulli variables, and with probability k/n the k coordinates in S are
independently chosen p-biased Bernoulli variables, and the rest are independently chosen q-biased
Bernoulli variables. The distributional (p, q)-planted densest k-subgraph problem is to find
the unknown subset S given access to samples from DS .
Our approach and lower bounds extend in a straightforward manner to this problem. In Section
5.2 we analyze this general setting and give lower bounds for all settings of p and q. Here we
describe a special case of our lower bounds when q = 1/2 and p = 1/2 + α. Our lower bound
becomes exponential as α becomes (inverse-polynomially) close to 0. Specifically:
Corollary 2.12. For any constant δ > 0, any k ≤ n1/2−δ , α > 0, ℓ ≤ min{k, 1/(4α2 )}, at least
nΩ(ℓ) queries to VSTAT(n2 /(48ℓα2 k2 )) are required to solve the distributional (1/2+α, 1/2)-planted
densest k-subgraph with probability at least 2/3.
For example, consider the setting k = ℓ = n1/3 and α = n−1/4 . It is not hard to see that for
this setting the problem can be solved on a random bipartite graph with n vertices on both sides
1/3
(in exponential time). Our lower bound for this setting implies that at least nΩ(n ) queries to
VSTAT(n3/2 ) will be required. Additional corollaries for the distributional (p, q)-planted densest
k-subgraph can be found in Section 5.2.
11

Relation to the planted k-biclique problem The upper and lower bounds we described for
statistical algorithms match the state of the art for the average-case planted k-biclique and planted
k-clique problems. Moreover, our lower bounds for the distributional versions of the planted kbiclique problem have implications for the hardness of the average-case planted k-biclique problem.
An instance of the latter problem is a random n × n bipartite graph with a k × k biclique planted
randomly. In Appendix A, we show that the average-case planted k-biclique is equivalent to our
distributional planted k-biclique with n samples. Specifically, a single sample corresponds to the
adjacency list of a vertex on the left, and n samples correspond to the adjacency matrix of the
bipartite graph. By this equivalence, an algorithm that solves the average-case planted bipartite
k-clique problem will also solve the distributional planted k-biclique with n samples. Our lower
bounds for the distributional problem therefore imply that the planted k-biclique problem would
require a non-statistical approach, i.e., one for which there is no statistical analogue.

2.5

Subsequent Work

In subsequent work, Feldman, Perkins and Vempala [2013] introduced a notion of statistical dimension that is based on the spectral norm of the correlation matrix of large sets of distributions. It is
always at least as large as the average correlation-based dimension defined here and also leads to
lower bounds on the complexity of SQ algorithms using VSTAT. Using this dimension they proved
tight lower bounds on the complexity of statistical algorithms for planted k-SAT and Goldreich’s
pseudo-random generator. In addition, they described statistical algorithms based on power iteration with nearly matching upper bounds. Finally, they demonstrate that lower bounds against SQ
algorithms can be used to derive concrete lower bounds for convex relaxations of the problem.
Feldman et al. [2013] have also extended the lower bounds against 1-STAT to lower bounds
against the k-bit version of 1-STAT at the expense of factor 2k blow-up in the number of queries.
Steinhardt, Valiant and Wager [2016] gave a more direct approach for proving lower bounds against
this oracle that is closely related to the techniques here and in Feldman et al. [2013]. They have
further showed that statistical queries can be used to simulate the oracle that that extracts k bits
from each sample in an interactive way (rather than at once).
Building on our approach, Feldman [2016] described new notions of statistical dimension and
proved that they tightly characterize the SQ complexity of solving general search problems over
distributions for both STAT and VSTAT oracle. He also simplified the analysis of VSTAT(t) by
√
showing that it
p
√ is equivalent (up to constant factors) to returning any value v such that | v −
ED [h]| ≤ 1/ t. Some additional recent applications of SQ lower bounds that are related to our
work include learning of the Ising model [Bresler et al., 2014], convex optimization [Feldman et al.,
2015] and distribution-independent PAC learning of lines over finite fields [Feldman, 2016].
The distributional planted k-biclique problem introduced here is a simple and natural problem that shows a remarkable property: information-theoretically it can be solved with many fewer
samples than is necessary for any known efficient algorithm (and no efficient statistical algorithm
exists). In particular, any algorithm that solves our problem with less than n samples will also
solve the average-case k-biclique problem (that is at least as hard as the usual planted k-clique
problem). In several more recent works, reductions from the planted clique problem were used
to demonstrate a similar phenomenon in a number of important problems in statistics and machine learning [Berthet and Rigollet, 2013, Ma and Wu, 2013, Hajek et al., 2015, Gao et al., 2014,
Wang et al., 2014, Cai et al., 2015].

12

3

Lower Bounds from Statistical Dimension

In this section we prove the general lower bounds. In later sections, we will compute the parameters
in these bounds for specific problems of interest.

3.1

Lower Bounds for Statistical Query Algorithms

We start by proving Theorem 2.7 which is the basis of all our lower bounds. In fact, we will prove
a stronger version of this theorem which also applies to randomized algorithms. For this version
we need an additional parameter in the definition of SDA.
Definition 3.1. For γ̄ > 0, η > 0, domain X and a search problem Z over a set of solutions F
and a class of distributions D over X, let d be the largest value such that there exists a reference
distribution D over X and a finite set of distributions DD ⊆ D with the following property: for any
solution f ∈ F the set Df = DD \ Zf has size at least (1 − η) · |DD | and SDA(Df , D, γ̄) ≥ d. We
define the statistical dimension with average correlation γ̄ and solution set bound η of Z to be d
and denote it by SDA(Z, γ̄, η).
Note that for any η < 1, SDA(Z, γ̄) ≥ SDA(Z, γ̄, η) and for η = 1−1/|DD |, we get SDA(Z, γ̄) =
SDA(Z, γ̄, η), where DD is the set of distributions that maximizes SDA(Z, γ̄).
Theorem 3.2. Let X be a domain and Z be a search problem over a set of solutions F and a class
of distributions D over X. For γ̄ > 0 and η ∈ (0, 1) let d = SDA(Z, γ̄, η). Any randomized SQ
algorithm that solves Z with probability α > η requires at least α−η
1−η d calls to VSTAT(1/(3γ̄)).
Theorem 2.7 is obtained from Theorem 3.2 by setting α = 1 and using any 1 − 1/|DD | ≤ η < 1.
Further, for any η < 1, SDA(Z, γ̄) ≥ SDA(Z, γ̄, η) and therefore for any η < 1, a bound on
SDA(Z, γ̄, η) can be used in Theorem 2.7 in place of bound on SDA(Z, γ̄). We now prove Theorem
3.2.
of Theorem 3.2. We prove our lower bound by exhibiting a distribution over inputs (which are
distributions over X) for which every deterministic SQ algorithm that solves Z with probability α
(over the choice of input) requires at least (α − η) · d/(1 − η) calls to VSTAT(1/(3γ̄)). The claim
of the theorem will then follow by Yao’s minimax principle [Yao, 1977].
Using the notation of Definition 3.1, let D be the reference distribution and DD be a set of
distributions for which the value d is achieved. Let A be a deterministic SQ algorithm that uses
q queries to VSTAT(1/(3γ̄)) to solve Z with probability α over the random and uniform choice of
a distribution from DD . Consider the execution of A in which to each query h of A, the oracle
+
⊆ DD be the set of distributions
returns exactly ED [h] and let f denote the output. Let the set DD
+
(recall that
on which A is successful for all valid responses of VSTAT(1/(3γ̄)). Let D + = Df ∩ DD
+
\ (DD \ Df ) and therefore
we defined Df = DD \ Zf ). We observe that D + = DD
+
| − |DD \ Df | ≥ α|DD | − |DD \ Df | =
|D + | ≥ |DD

α|DD | − |DD \ Df |
α−η
|Df | ≥
|Df |.
|DD | − |DD \ Df |
1−η

(1)

By the definition of SDA(Z, γ̄), it holds that SDA(Df , D, γ̄) ≥ d. In Lemma 3.3 given below,
we will show that under the conditions of this proof, SDA(Df , D, γ̄) ≥ d implies that A must use
at least q ≥ d|D + |/|Df | queries. By inequality (1), q ≥ α−η
1−η · d giving the desired lower bound.
13

The proof of Theorem 3.2 relies on the following lemma that translates a lower bound on
SDA(Df , D, γ̄) into a lower bound on the number of queries that A needs to use. Its proof is based
on ideas from [Szörényi, 2009] and [Feldman, 2012].
Lemma 3.3. Let X be a domain and Z be a search problem over a set of solutions F and a class of
distributions D over X. Let A be a (deterministic) SQ algorithm for Z that uses at most q queries
to VSTAT(1/(3γ̄)). For a distribution D, consider the execution of A on D in which to each query
h of A, the oracle returns exactly ED [h] and let f denote the output. For a set of distributions
Df ⊆ D \ Zf and γ̄ > 0, let d = SDA(Df , D, γ̄). Let D + be the set of all distributions in Df for
which A successfully solves Z for all valid responses of VSTAT(1/(3γ̄)). Then q ≥ d · |D + |/|Df |.
Proof. Let h1 , h2 , . . . , hq be the queries asked by A when executed on D with the exact responses
of the oracle. Let m = |D + | and we denote the distributions in D + by {D1 , D2 , . . . , Dm }. For every
k ≤ q, let Ak be the set of all distributions Di such that
)
( r
pi,k (1 − pi,k )
1
.
,
,
E[hk (x)] − E [hk (x)] > τi,k = max
t
t
Di
D
where we use t to denote 1/(3γ̄) and pi,k to denote EDi [hk (x)]. To prove the desired bound we first
prove the following two claims:
P
1.
k≤q |Ak | ≥ m;
2. for every k ≤ q, |Ak | ≤ |Df |/d.

Combining these two implies that q|Df |/d ≥ m or, equivalently, q ≥ d|D + |/|Df |.
In the rest of the proof for conciseness we drop the subscript D from inner products and norms.
To prove the first claim we assume, for the sake of contradiction, that there exists Di 6∈ ∪k≤q Ak .
Then for every k ≤ q, | ED [hk (x)] − EDi [hk (x)]| ≤ τi,k . This implies that ED [hk (x)] are within
τi,k of EDi [hk (x)]. By the definition of VSTAT(t), this implies that the responses we used in our
execution of A on D are also valid responses of VSTAT(t) when A is executed on Di . The output
of this execution is f and hence it must be a valid solution for Di . This contradicts the definition
of D + since it is a subset of Df ⊆ D \ Zf .
To prove the second claim, suppose that for some k ∈ [d], |Ak | > |Df |/d. Let pk = ED [hk (x)]
and assume that pk ≤ 1/2 (when pk > 1/2 we just replace hk by 1 − hk in the analysis below).
First we note that:




Di
Di (x)
hk (x) − E[hk (x)] = hk ,
− 1 = pi,k − pk .
E [hk (x)] − E[hk (x)] = E
D(x)
D
D
D
D
Di
i (x)
Let D̂i (x) = D
D(x) − 1, (where the convention is that D̂i (x) = 0 if D(x) = 0). We will next show
upper and lower bounds on the following quantity
*
+
X
Φ = hk ,
D̂i · signhhk , D̂i i .

Di ∈Ak

14

By Cauchy-Schwartz we have that
2

Φ =

*

hk ,

X

Di ∈Ak

+2

D̂i · signhhk , D̂i i

2
2

≤ khk k ·

X

Di ∈Ak



≤ khk k2 · 

D̂i · signhhk , D̂i i

X

Di ,Dj ∈Ak

2



hD̂i , D̂j i 

≤ khk k · ρ(Ak , D) · |Ak |2 .

(2)

We also have that
Φ2 =

*

hk ,

X

Di ∈Ak

+2

D̂i · signhhk , D̂i i



2

= 

X

hhk , D̂i i · signhhk , D̂i i

≥ 

X

|pi,k − pk | .

Di ∈Ak



Di ∈Ak

2

(3)

p
pi,k (1 − pi,k )/t}.
To evaluate the last term of this inequality we use the fact that |pi,k −pk | ≥ τi,k = max{1/t,
p
Next we use a simple fact (proved in Lemma 3.5 below) that |pi,k −pk | ≥ max{1/t, pi,k (1 − pi,k )/t}
q
implies that |pk − pi,k | ≥ min{pk3t,1−pk } to obtain: For every Di ∈ Ak ,
|pk − pi,k | ≥

r

min{pk , 1 − pk }
=
3t

r

pk
.
3t

(4)

By substituting equation (4) into (3) we get that Φ2 ≥ p3tk · |Ak |2 .
We note that, hk is a [0, 1]-valued function and therefore khk k2 ≤ pk . Substituting this into
equation (2) we get that Φ2 ≤ pk · ρ(Ak , D) · |Ak |2 . By combining these two bounds on Φ2 we obtain
that ρ(Ak , D) ≥ 1/(3t) = γ̄ which contradicts the definition of SDA.
Remark 3.4. We remark that for algorithms using the STAT oracle, the proof can be simplified
√
somewhat. For τ = γ̄,
2

X
|pi,k − pk | ≥ τ 2 |Ak |2
Φ2 ≥ 
Di ∈Ak

and the proof could be obtained by directly combining equations (2) and (3) to get a contradiction.
This also eliminates the factor of 3 in the bound and the assumption that queries are [0, 1]-valued
can be relaxed to [−1, 1]-valued queries since it suffices that khk k2 ≤ 1. This leads to an identical
√
lower bound on the number of queries for STAT( γ̄) in place of VSTAT(1/(3γ̄)).
We now prove a bound on the distance between any p ∈ [0, 1] and p′ which is returned by
VSTAT(t) on a query with expectation p in terms of p′ that we used in the proof of Lemma 3.3.
′
′
Lemma
3.5. For
 an integer t andqany p ∈ [0, 1], let p ∈ [0, 1] be such that |p − p| ≥ τ =
 q
′
′
. Then |p′ − p| ≥ min{p3t,1−p } .
max 1t , p(1−p)
t

15

Proof. First note that our conditions and bounds do not change if we replace both p and p′ with
1 − p and 1 − p′ , respectively.p
Therefore it is sufficient to prove the bound when p ≤ 1/2. We know
that |p′ − p| ≥ τ = max{1/t, p(1 − p)/t}. If p ≥ 2p′ /3 then certainly
s
r
r
2 ′ 1
p(1 − p)
p′
′
3p · 2
≥
=
.
|p − p| ≥
t
t
3t
′
′
′
′
′
′
Otherwise (when p <
q2p /3), p − p ≥ p − 2p /3 = p /3. We also know that |p − p | ≥ τ ≥ 1/t and
p′
.
therefore |p − p′ | ≥ 3t

3.1.1

Decision Problems

For decision problems, our dimension and lower bounds can be simplified. We denote by B(D, D)
a decision problem in which the input distribution D ′ either equals D or belongs to D and the
goal of the algorithm is to identify whether D ′ = D or D ′ ∈ D. For example, for the distributional
planted k-biclique problem, the decision version is to determine whether the given input distribution
corresponds to a planted k-biclique or to one with no planting (uniform distribution on {0, 1}n .
For the decision problem B(D, D) our notion of dimension simplifies to the following.
Definition 3.6. For γ̄ > 0, domain X and a decision problem B(D, D), let SDA(B(D, D), γ̄) be
defined as the largest value d such that there exists a finite set of distributions DD ⊆ D such that
SDA(DD , D, γ̄) = d.
Our technique gives the following lower bound for decision problems:
Theorem 3.7. Let D be a distribution and D be a set of distributions over a domain X such
that for some γ̄, SDA(B(D, D), γ̄) = d. Any (randomized) SQ algorithm that solves B(D, D) with
success probability α > 1/2 requires at least (2α − 1)d queries to VSTAT(1/(3γ̄)).
Proof. As before, we exhibit a hard distribution over input distributions for which every deterministic SQ algorithm that solves B(D, D) with probability α (over the choice of input) requires at
least (2α − 1)d queries to VSTAT(1/(3γ̄)). Let DD be the set of distributions that witnesses the
statistical dimension, namely, SDA(DD , D, γ̄) = d. Consider the following distribution over the
input distribution D ′ : D ′ equals D with probability 1/2 and D ′ equals a random uniform element
of DD with probability 1/2.
A has success probability α > 1/2 and therefore, when executed on D with exact responses to
queries, it must correctly identify D (say it outputs 0 in this case). We then define D + ⊆ DD as
the set of distributions on which A is successful (that is outputs 1). The probability of success of
A implies that |D + | ≥ (2α − 1)|DD |. Now, the set DD is included in the set of distributions D for
which 0 is not a valid solution. Therefore we can apply Lemma 3.3 with Df = DD to obtain that
the number of queries to VSTAT(1/(3γ̄)) is q ≥ (2α − 1)d.

3.2

Statistical Dimension Based on Pairwise Correlations

In addition to SDA which is based on average correlation we introduce a simpler notion based on
pairwise correlations. It is sufficient for some applications and is easy to relate to SQ-DIM used in
learning (as we do in Section 6).
16

Definition 3.8. We say that a set of m distributions D = {D1 , . . . , Dm } over X is (γ, β)-correlated
relative to a distribution D over X if:
(


β for i = j ∈ [m]
Dj
Di
− 1,
−1
≤
D
D
γ for i 6= j ∈ [m].
D
Definition 3.9. For γ, β > 0, domain X and a search problem Z over a set of solutions F and
a class of distributions D over X, let m be the largest integer such that there exists a reference
distribution D over X and a finite set of distributions DD ⊆ D such that for any solution f ∈ F,
Df = DD \Zf is (γ, β)-correlated relative to D and |Df | ≥ m. We define the statistical dimension
with pairwise correlations (γ, β) of Z to be m and denote it by SD(Z, γ, β).
For decision problems SD(B(D, D), γ, β) is defined as the largest integer m such that there exists
a set of distributions DD ⊆ D of size m that is (γ, β)-correlated relative to D.
It is easy to bound SDA of any (γ, β)-correlated set of distributions.
Lemma 3.10. Let D = {D1 , D2 , . . . , Dm } be a (γ, β)-correlated set of distributions relative to a
mγ ′
distribution D. Then for every γ ′ > 0, SDA(D, D, γ + γ ′ ) ≥ β−γ
.
Proof. Take d = mγ ′ /(β − γ); we will prove that SDA(D, D, γ + γ ′ ) ≥ d. Consider a set of
distributions D ′ ⊆ D, where |D ′ | ≥ |D|/d ≥ m/d = (β − γ)/γ ′ :


X
1
D1
D2
′
ρ(D , D) = ′ 2
− 1,
−1
|D |
D
D
D
′
D1 ,D2 ∈D


1
|D ′ |β + (|D ′ |2 − |D ′ |)γ
′
2
|D |
β−γ
≤γ+
|D ′ |
≤ γ + γ′

≤

As an immediate corollary we obtain a bound on SDA of a search or decision problem from a
bound on SD.
Corollary 3.11. Let X be a domain and Z be a search or decision problem over a set of solutions
F and a class of distributions D over X. For γ, β > 0, let m = SD(Z, γ, β). Then for every γ ′ > 0,
mγ ′
SDA(Z, γ + γ ′ ) ≥ β−γ
.
We now apply Theorem 2.7 to obtain the following lower bound on SQ algorithms in terms of
SD.
Corollary 3.12. Let X be a domain and Z be a search or decision problem over a set of solutions
F and a class of distributions D over X. For γ, β > 0, let m =√SD(Z, γ, β). For any γ ′ > 0, any
SQ algorithm requires at least mγ ′ /(β − γ) queries to the STAT( γ + γ ′ ) or VSTAT(1/(3(γ + γ ′ )))
oracle to solve Z.
−2/3

In this corollary if, for example, SD(Z, γ = m 2 , β = 1) ≥ m then at least m1/3 /2 queries to
VSTAT(m2/3 /3) or STAT(m−1/3 ) oracle are required to solve the problem.
17

3.3

Lower Bounds for 1-bit Sampling Algorithms

Next we address lower bounds on algorithms that use the 1-STAT oracle. We recall that the
1-STAT oracle returns the value of a function on a single randomly chosen point. To estimate the
expectation of a function, an algorithm can simply query this oracle multiple times with the same
function and average the results.
We note that responses of 1-STAT do not have the room for the possibly adversarial deviation
afforded by the tolerance of the STAT and VSTAT oracles. The ability to use these slight deviations
in a coordinated way is used crucially in our lower bounds against VSTAT and in all known
lower bounds for SQ learning algorithms. While it is possible to derive lower bounds against
1-bit sampling algorithms using m queries from lower bounds against algorithms that use O(m)
queries to STAT(1/m) [Ben-David and Dichterman, 1998], such lower bound will not suffice for our
main application. It would only imply the trivial lower bound of Ω(n/k) queries to 1-STAT for
the planted k-biclique problem. Proving tighter lower bounds against 1-bit sampling algorithms
directly is harder and indeed lower bounds for the equivalent Honest SQ learning model required a
substantially more involved argument than lower bounds for the regular SQ model [Yang, 2005].
Our lower bounds for 1-bit sampling algorithms rely on a direct simulation of the 1-STAT oracle
using the VSTAT oracle. This simulation allows us to derive lower bounds against 1-bit sampling
algorithms from Theorem 3.2. We also provide a reverse simulation of VSTAT oracle using 1-STAT
oracle.
Theorem 3.13. Let Z be a search problem and let A be a (possibly randomized) 1-bit sampling
algorithm that solves Z with probability at least α using m samples from 1-STAT. For any δ ∈
(0, 1/4], there exists a SQ algorithm A′ that uses at most m queries to VSTAT(m/δ2 ) and solves
Z with probability at least α − δ.
Our proof relies on a simple simulation. Given query h1 : X → {0, 1} from A to 1-STAT,
we make the same query h1 to VSTAT(t) for t = m/δ2 . Let p′1 be the response. We flip a coin
with bias p′1 (that is one that outputs 1 with probability p′1 and 0 with probability 1 − p′1 ) and
return it to the algorithm. We do the same for the remaining m − 1 queries which we denote by
h2 , h3 , . . . , hm . We then prove that the true m samples of 1-STAT and our simulated coin flips are
statistically close by upper bounding the expected ratio of their density functions (which is equal
to the χ2 divergence plus 1) . This implies that the success probability of the simulated algorithm
is not much worse than that of the 1-bit sampling algorithm.
In our proof we will, for simplicity and without loss of generality, assume that VSTAT(t) always
outputs a value in the interval [1/t, 1− 1/t]. We can always replace a value v returned by VSTAT(t)
by v ′ which is the closest value to v in the above interval. It is easy to see that if v is a valid answer
of VSTAT(t) then so is v ′ .
We will need the following lemmas for our proof. The first one bounds the total variation
distance between two distributions in terms of the expected ratio of probability density functions.
Lemma 3.14. Let D1 and D2 be two distribution over a domain X of finite2 size such that D2 (x)
is non-vanishing. Denote the total variation
h
idistance between D1 and D2 by ∆T V (D1 , D2 ). Then
√
D1 (x)
∆T V (D1 , D2 ) ≤ ρ/2, where ρ = ED1 D2 (x) − 1.
2

This assumption is simply for convenience of notation. It holds in our applications.

18

Proof. The key observation is that the χ2 -divergence between D1 and D2 is exactly the expected
ratio minus 1.
"

2 #

 2


 2
D1 (x)
D1 (x)
D1 (x)
D1 (x)
D1 (x)
.
+1 = E
−1
−1= E
ρ= E
−1= E
−2
2
2
D2 (x)
D2 (x)
D2
D2 D2 (x)
D1 D2 (x)
D2 D2 (x)
By Jensen’s inequality this implies that
E

D2



D1 (x)
−1
D2 (x)



Finally,

v "
u
2 #

u
√
D1 (x)
t
= ρ.
−1
≤ E
D2 (x)
D2


 √
ρ
1X
1
D1 (x)
∆T V (D1 , D2 ) =
|D1 (x) − D2 (x)| = E
−1 ≤
.
2
2 D2 D2 (x)
2
x∈X

The second lemma is that if p′ is an answer of VSTAT(t) for a query h, such that ED [h] = p,
then the expected ratio of density functions of Bernoulli random variables with biases p and p′ ,
denoted B(p) and B(p′ ), is small.

 q
p(1−p)
1
′
′
.
Lemma 3.15. For an integer t and p ∈ [0, 1] let p ∈ [1/t, 1−1/t] such that |p −p| ≤ max t ,
t
Then

E

b∼B(p)



Pr[B(p) = b]
Pr[B(p′ ) = b]



3
≤1+ .
t

Proof. If b = 1, the ratio is p/p′ and when b = 0, then it is (1 − p)/(1 − p′ ). Thus, the expected
ratio is
p2 (1 − p)2
(p − p′ )2
+
=
1
+
.
p′
1 − p′
p′ (1 − p′ )

We can assume without loss of generality that p′ ≤ 1/2.
Now if p ≤ 3p′ then p(1 − p) ≤ 3p′ (1 − p′ ). Otherwise (when, p > 3p′ ), we know that p ≥ 3p′ ≥
3/t. This implies that p − p′ ≥ 2p/3 ≥ 2/t. This means that
r
r
2p
p(1 − p)
p
′
≤p−p ≤
≤
.
3
t
t
This can only be true when p ≤ (3/2)2 /t = 9/(4t), contradicting our assumption that p ≥ 3/t.
This implies that
( r
)
( r
) r
1
1
p(1 − p)
3p′ (1 − p′ )
3p′ (1 − p′ )
max
≤ max
≤
,
,
.
t
t
t
t
t
By using this bound in the ratio equation we get that
3p′ (1−p′ )

(p − p′ )2
3
1+ ′
≤1+ ′ t ′ ≤1+ .
p (1 − p′ )
p (1 − p )
t

19

We can now complete the proof of Theorem 3.13.
of Theorem 3.13. We simulate A using VSTAT(t) as described above. We now prove that for
any algorithm the total variation distance between the true answers of 1-STAT and the simulated
distribution is at most δ. Formally, let R denote the set of all outcomes of A’s random bits
and for r ∈ R, let Ar denote the execution of A when its random bits are set to r. let ΠA
denote the distribution over the m bits obtained by the algorithm A when it is run with 1-STAT
oracle. Similarly, let Π′A denote the distribution over {0, 1}m obtained by running the algorithm A
simulated using VSTAT(t) as above. By definition, ΠA = Er∈R ΠAr and similarly Π′A = Er∈R Π′Ar .
This implies that,


∆T V (ΠA , Π′A ) ≤ E ∆T V (ΠAr , Π′Ar ) ≤ max ∆T V (ΠAr , Π′Ar ).
r∈R

r∈R

The algorithm Ar is deterministic and it is therefore sufficient to prove the bound on total variation
distance for deterministic algorithms. For conciseness we assume henceforth that A is deterministic.
For any i ∈ [m] let ΠAi denote the probability distribution on the first i samples of A executed
with 1-STAT. For j ≤ i let z j denote the first j bits of z. Let ΠAi (z | z i−1 ) denote the probability
that the first i samples of A executed with 1-STAT oracle are equal to z conditioned on the
probability that the first i − 1 samples are equal to z i−1 . We define Π′Ai (z) and Π′Ai (z | z i−1 )
analogously. We also denote by hz the query that A asks after getting z as the response to first i
samples and let pz = ED [hz ]. Let p′z denote the response of VSTAT(t) on hz .
For i ∈ [m] and any z ∈ {0, 1}i , ΠAi (z | z i−1 ) = Pr[B(pz i−1 ) = zi ] and hence ΠAi (z) =
ΠAi−1 (z i−1 ) Pr[B(pz i−1 ) = zi ]. Similarly, Π′Ai (z | z i−1 ) = Pr[B(p′z i−1 ) = zi ] and Π′Ai (z) =
Π′Ai−1 (z i−1 ) Pr[B(p′z i−1 ) = zi ]. This implies that:
#
#
"
"
ΠAi−1 (z i−1 ) Pr[B(pz i−1 ) = zi ]
ΠAi (z)
= E
E
′
′
′
z∼ΠAi ΠAi−1 (z i−1 ) Pr[B(pz i−1 ) = zi ]
z∼ΠAi ΠAi (z)
"
#

ΠAi−1 (y)
Pr[B(py ) = b]
.
· E
=
E
′
′
y∼ΠAi−1 ΠA
b∼B(py ) Pr[B(py ) = b]
i−1 (y)

Now by Lemma 3.15, this implies that for any z of length i ∈ [m],
"
#
"
# 

ΠAi−1 (y)
ΠAi (z)
2
≤
· 1+
.
E
E
′
′
t
z∼ΠAi ΠAi (z)
y∼ΠAi−1 ΠA
i−1 (y)
Applying this iteratively we obtain that
 


3 m
ΠA (z)
≤ e3m/t .
≤ 1+
E
′
t
z∼ΠA ΠA (z)
3m/t ≤ 1 + 4m/t. By
By our definition, t = m/δ2 ≥ 16m. Therefore,
3m/t ≤ 1/5 and
p hence e
p
′
Lemma 3.14, we get that ∆T V (ΠA , ΠA ) ≤ (1 + 4m/t − 1)/2 = m/t = δ. This implies that the
success probability of A using the simulated oracle is at least α − δ.

We now combine Theorems 3.7 and 3.13 to obtain the following lower bound for decision problems.
20

Theorem 3.16. Let X be a domain and D be a distribution over X and D be a set of distributions
over X. For γ̄ > 0, let d = SDA(B(D, D), γ̄). Any 1-bit sampling algorithm that solves B(D, D)
with probability α requires at least m queries to 1-STAT for


d(2α − 1) (2α + 1)2
,
.
m = min
2
48γ̄
In particular, any algorithm with success probability of at least 2/3 requires at least min{d/6, 1/(432γ̄ )}
queries to 1-STAT.
Proof. Assuming the existence of a 1-bit sampling algorithm using less than m queries, we apply
Theorem 3.13 for δ = (2α − 1)/4 to simulate the algorithm using VSTAT. The bound on m ensures
1
that the resulting algorithm uses less than d(2α − 1)/2 queries to VSTAT( 3γ̄
) and has success
probability of at least α − δ = (2α + 1)/4. By substituting these parameters into Theorem 3.7 we
obtain a contradiction.
For general search problems this leads to the following lower bound.
Theorem 3.17. Let X be a domain and Z be a search problem over a set of solutions F and a
class of distributions D over X. For γ̄ > 0 and η ∈ (0, 1), let d = SDA(Z, γ̄, η). Any (possibly
randomized) 1-bit sampling algorithm that solves Z with probability α requires at least m calls to
1-STAT for


d(α − η) (α − η)2
,
.
m = min
2(1 − η)
12γ̄

In particular, if η ≤ 1/6 then any algorithm with success probability of at least 2/3 requires at least
min{d/4, 1/(48γ̄)} queries to 1-STAT.

To conclude, we formally state a simple reduction in the other direction, namely that VSTAT(t)
oracle can be simulated using the 1-STAT oracle. It has been observed that, given a Boolean query
function h one can obtain an estimate of ED [h] using t = O(log(1/δ)/τ 2 ) 1-bit samples which with
probability at least 1 − δ will be within τ of ED [h] [Ben-David and Dichterman, 1998]. Using the
multiplicative Chernoff bound, it is not hard to see that O(t log(1/δ)) samples are sufficient to
estimate p = ED [h] within tolerance guaranteed by VSTAT(t). In addition, we will show how to
use 1-STAT oracle to estimate the expectation of real-valued queries.
Theorem 3.18. Let t, q > 0 be any integers and δ > 0. There exists an algorithm A′ that for any
input distribution D and any algorithm A that asks at most q queries to VSTAT, with probability
at least 1 − δ, provides valid for VSTAT(t) answers to all the queries of A. A′ uses O(qt · log(q/δ))
queries to 1-STAT for the same input distribution D.
Proof. For every query h : X → [0, 1] of A, the algorithm A′ estimates p = ED [h] as follows. To
generate a random Bernoulli variable with bias p, B draws θ ∈ [0, 1] randomly and uniformly and
defines: hθ (x) = 1 if h(x) ≤ θ and hθ (x) = 0 otherwise. It then makes the query hθ to 1-STAT.
Observe that
Pr [hθ (x) = 1] = E [Pr[hθ (x) = 1]] = E [h(x)] = p.
θ,x∼D

x∼D θ

x∼D

The algorithm B repeats this m times (each time choosing a new random θ) and then answers the
query h with the mean of the obtained samples (for m to be defined later). We denote the mean
by v.
21

Assuming that p ≤ 1/2, multiplicative Chernoff bounds imply that
h
i
p
Pr |v − p| ≥ p(1 − p)/t ≤ 2e−3mp/(p(1−p)t) ≤ 2e−6m/t .

The bound in the case of p > 1/2 follows from the symmetric
p argument.
Choosing m = 6t · ln(2q/δ) ensures that Pr[|v − p| ≥ p(1 − p)/t] ≤ δ/q. This implies that
q arbitrary queries for VSTAT(t) can be answered correctly with probability at least 1 − δ using
6qt · ln(2q/δ) queries to 1-STAT.

4

Warm-up: MAX-XOR-SAT

In this section, we demonstrate our techniques on a warm-up problem, MAX-XOR-SAT. For this
problem, it is sufficient to use pairwise correlations, rather than average correlations.
For ǫ ≥ 0, the ǫ-approximate MAX-XOR-SAT problem is defined as follows. Given samples
from some unknown distribution D over XOR clauses on n variables, find an assignment that
maximizes up to additive error ǫ the probability a random clause drawn from D is satisfied.
In the worst case, it is known that MAX-XOR-SAT is NP-hard to approximate to within
1/2 − δ for any constant δ [Håstad, 2001]. In practice, local search algorithms such as WalkSat [Selman et al., 1995] are commonly applied as heuristics for maximum satisfiability problems.
We give strong evidence that the distributional version of MAX-XOR-SAT is hard for algorithms
that locally seek to improve an assignment by flipping variables as to satisfy more clauses, giving
some theoretical justification for the observations of [Selman et al., 1995]. Moreover, our proof even
applies to the case when there exists an assignment that satisfies all the clauses generated by the
target distribution.
The bound we obtain can be viewed as a restatement of the known lower bound for learning
parities using statistical query algorithms (indeed, the problem of learning parities is a special case
of our distributional MAX-XOR-SAT).
To formalize the search problem, we will denote by C = {0, 1}n the set of XOR clauses in n
variables, such that for c ∈ C, if for i ∈ [n] we have ci = 1 then the ith variable appears in c, and
otherwise it does not; for simplicity, no variables are negated in the clauses. Let A = {0, 1}n denote
the set of possible assignments to the variables. We will say that the assignment a ∈ A satisfies the
clause c ∈ C if a · c = 1 (where a · c denotes the inner product modulo 2).
Let D be the set of distributions over clauses in C. For a distribution D ∈ D and an assignment
a ∈ A, let fD (a) = Ec∼D [a · c] be the fraction of clauses that a satisfies under D. For D ∈ D let
MD = maxa∈A fD (a). The MAX-XOR-SAT problem asks to find a ∈ A that maximizes fD (a),
given samples from an unknown distribution D.
We are now ready to formalize the search problem that we are interested in, using the notation
above and that of Definition 2.1.
Problem 4.1. (ǫ-approximate MAX-XOR-SAT) Let X = C = {0, 1}n (the set of clauses), D be
the set of distributions over X, F = A = {0, 1}n (the set of assignments). Let Z : D → 2F be
defined as Z(D) = {a ∈ A | fD (a) ≥ MD − ǫ}.
Theorem 4.2. For any δ > 0, any SQ algorithm requires at least 2n/3 − 1 queries to STAT(2−n/3 )
to solve 21 − δ -approximate MAX-XOR-SAT.
22

We will first determine the statistical dimension of our search problem. This will immediately
imply Theorem 4.2 using Corollary 3.11 (by choosing γ ′ = 2−n/3 ).
Lemma 4.3. For a δ > 0, let Z denote the (1/2 − δ)-approximate MAX-XOR-SAT. Then the
statistical dimension of Z with pairwise correlation (γ, β) = (0, 1) is SD(Z, 0, 1) ≥ 2n − 1.
Proof. We verify the properties of Definition 3.9.
Let the reference distribution D = UC , the uniform distribution over C = {0, 1}n . For a ∈
A = {0, 1}n = F, let Da ∈ D be the uniform distribution over c ∈ C such that a · c = 1. Let
DD = {Da | a ∈ A}, so |DD | = 2n .
For a, b ∈ A, we have


X
1
1 .
fDa (b) = E [b · c] = n−1 
2
c∼Da
c∈C | a·c=1,b·c=1

Note that if b = a then fDa (b) = 1, and if b 6= a, fDa (b) = 1/2 (indeed, |{c ∈ C | a · c = 1, b · c =
1}| = 2n /4 since it is the size of two intersecting affine subspaces in {0, 1}n ).
Therefore, for a ∈ A and ǫ = 1/2 − δ > 0, the set of solutions is
Z(Da ) = {b ∈ A | fDa (b) ≥ 1/2 + δ} = {a},

and so Za = {Da }.
To conclude the proof we will show that for any assignment a ∈ F = A the set Da = DD \ {Da }
of distributions is (0, 1)-correlated (see Definition 3.8).
Note that for a ∈ A, and c ∈ C,
(


−1 if c · a = 0
Da
− 1 (c) =
D
1 if c · a = 1.

In other words, DDa − 1 (c) = −(−1)a·c . A well-known (and easy to verify) property of {−1, 1}valued parity functions is that they are (0, 1)-correlated over the uniform distribution. That is, for
a, b ∈ A
(


0 for a = b
Da
Db
− 1,
−1
≤
D
D
1 for a 6= b.
D

5
5.1

Planted Biclique and Densest Subgraph
Statistical Dimension of Planted Biclique

We now prove the lower bound claimed in Theorem 2.9 on the problem of detecting a planted
k-biclique in the given distribution on vectors from {0, 1}n as defined above.
Throughout this section we will use the following notation. For a subset S ⊆ [n], let DS be the
distribution over
{0, 1}n with a planted set S. Let Sk denote the set of all nk subsets of [n] of size

k and m = nk . We index the elements of Sk in some arbitrary order as S1 , . . . , Sm . For i ∈ [m],
23

we use Di to denote DSi . We will also assume, whenever necessary, that k and n are larger than
some fixed constant.
The reference distribution in our lower bounds will be the uniform distribution over {0, 1}n and
let D̂S denote DS /D − 1. In order to apply our lower bounds based on statistical dimension with
average correlation we now prove that for the planted biclique problem average correlations of large
sets of distributions must be small. We start with a lemma that bounds the correlation of two
planted biclique distributions relative to the reference distribution D as a function of the overlap
between the planted sets:
Lemma 5.1. For i, j ∈ [m],
D
E
D̂i , D̂j

ρD (Di , Dj ) =

D

where λ = |Si ∩ Sj |.

≤

2λ k2
,
n2

Proof. For the distribution Di , we consider the probability Di (x) of generating the vector x. Then,
(
1
k
1
( n−k
if ∀s ∈ Si , xs = 1
n ) 2n + ( n ) 2n−k
Di (x) =
n−k 1
( n ) 2n otherwise.
Now we compute the vector D̂i =

Di
D

Di
−1=
D

− 1:
(
k

k2
n
− nk

−

k
n

if ∀s ∈ Si , xs = 1
otherwise.

We then bound the inner product:
D

D̂i , D̂j

E

D

≤
≤

2n−2k+λ
2n
2λ k2
,
n2



k2k
k
−
n
n

2

+2



2n−k
2n−2k+λ
−
2n
2n



k2k
k
−
n
n



k
−
n





k
+ −
n

2

D
E
which holds when k ≥ 3. We also note that D̂i , D̂j
≥ 0.
D

We now give a bound on the average correlation of any D̂S with a large number of distinct
biclique distributions.
Lemma 5.2. Let δ ≥ 1/ log n and k ≤ n1/2−δ . For any integer ℓ ≤ k, S ∈ Sk and any set A ⊆ Sk
where |A| ≥ 3(m − 1)/n2ℓδ ,
k2
1 X
hD̂S , D̂i i < 2ℓ+1 2 .
|A|
n
Si ∈A

Proof. In this proof we first show that if the total number of sets in A is large then most of sets
in A have a small overlap with S. We then use the bound on the overlap of most sets to obtain a
bound on the average correlation of DS with distributions for sets in A.
24

k2
n2

Formally, we let α =
over Si ∈ A,

and using Lemma 5.1 get the bound |hD̂i , D̂j i| ≤ 2|Si ∩Sj | α. Summing
X

Si ∈A

hD̂S , D̂i i ≤

X

2|S∩Si | α.

Si ∈A

For any set A ⊆ Sk of size t this bound is maximized when the sets of A include S, then all sets
that intersect S in k − 1 indices, then all sets that intersect S in k − 2 indices and so on until the
size bound t is exhausted. We can therefore assume without loss of generality that A is defined in
precisely this way.
Let Tλ = {Si | |S ∩ Si | = λ} denote the subset of all k-subsets that intersect with S in exactly
λ indices. Let λ0 be the smallest λ for which A ∩ Tλ is non-empty. We first observe that for any
1 ≤ j ≤ k − 1,
k  n−k 
|Tj |
(j + 1)(n − 2k + j + 1)
(j + 1)(n − 2k)
j k−j
= k  n−k  =
≥
≥
2
2
|Tj+1 |
(k
−
j)
(k
−
j)
j+1 k−j−1
≥

(j + 1)(1 − 2n−1/2−δ )
(j + 1)n2δ
(j + 1)(n − 2n1/2−δ )
.
≥
≥
1−2δ
−2δ
n
n
2

(5)

By applying this equation inductively we obtain,
|Tj | ≤

2j · |T0 |
2j · (m − 1)
<
j! · n2δj
j! · n2δj

where the last inequality holds since |T0 | ≤ m − 2 whenever n ≥ 2k + 1. For n larger than some
fixed constant
X

k≥λ≥j

|Tλ | <

X 2λ · (m − 1)
3(m − 1)
2λ
m−1 X
≤
≤
.
2δλ
2δj
2δ(λ−j)
λ! · n
n
n2δj
λ! · n
k≥λ≥j
k≥λ≥j

P
By definition of λ0 , |A| ≤ j≥λ0 |Tj | < 3(m − 1)/n2δλ0 . In particular, if |A| ≥ 3(m − 1)/n2ℓδ then
n2δλ0 < n2ℓδ or λ0 < ℓ. Now we can conclude that
X

Si ∈A

hD̂S , D̂i i ≤

k
X

j=λ0

2j |Tj ∩ A|α



≤ 2λ0 |Tλ0 ∩ A| +


k
X

j=λ0 +1



2j |Tj | α


≤ 2λ0 |Tλ0 ∩ A| + 2 · 2λ0 +1 |Tλ0 +1 | α
< 2λ0 +2 |A|α ≤ 2ℓ+1 |A|α.

To derive the second to last inequality we need to note that for every j ≥ 0, 2j |Tj | > 2(2j+1 |Tj+1 |)
whenever n2δ ≥ 4. We can therefore telescope the sum.
We can now bound the statistical dimension (with average correlation) of the planted k-biclique
problem.
25

Theorem 5.3. For δ ≥ 1/ log n and k ≤ n1/2−δ
let Z the distributional planted k-biclique problem.
n
ℓ+1
2
2
Then for any ℓ ≤ k, SDA(Z, 2 k /n , 1/ k ) ≥ n2ℓδ /3. In addition, let D be the uniform distribution and denote the set of all planted distributions by D. Then, SDA(D, D, 2ℓ+1 k2 /n2 ) ≥ n2ℓδ /3.

Proof. For every solution S ∈ F, ZS = {DS } and let DS = D \ {DS }. Note that |DS | = nk − 1
and therefore |DS | ≥ (1 − 1/ nk )|D|. This means that we can use 1/ nk as the solution set bound.
Let D ′ be a set of distributions D ′ ⊆ DS such that |D ′ | ≥ 3(m − 1)/n2ℓδ . Then by Lemma 5.2,
for every Si ∈ D ′ ,
2
1 X
ℓ+1 k
.
h
D̂
,
D̂
i
<
2
i
j
|D ′ |
n2
′
Sj ∈D

ℓ+1 k 2
n2

In particular, ρ(D ′ , D) < 2
. By the definition of SDA (Definition 3.1), this means that
n
ℓ+1
2
2
2ℓδ
SDA(Z, 2 k /n , 1/ k ) ≥ n /3.
The second claim holds by exactly the same argument since |D ′ | ≥ m/d implies |D ′ | ≥ (m −
1)/d.
For a positive r we choose ℓ = log r−1. Our lower bound for the planted bi-clique problem stated
in Theorem 2.9 follows from substituting the bound SDA(Z, rk 2 /n2 , 1/ nk ) ≥ n2(log(r)−1)δ /3 into
Theorem 3.2 (with η = 1/ nk and δ = 2/3). In addition, by Theorem 3.7 used with α = 1/2 + 1/t,
we obtain hardness of the decision version of the problem for randomized SQ algorithms which also
implies Theorem 2.9.
Theorem 5.4. For any constant δ > 0, any k ≤ n1/2−δ and r > 0, let D be the uniform distribution
over {0, 1}n and D be the set of all planted k-biclique distributions. For some t = nΩ(log r) , any
randomized SQ algorithm that solves the decision problem B(D, D) with probability 1/2+1/t requires
t queries to VSTAT(n2 /(rk 2 )).
Theorem 3.13 used with δ = 1/9 implies that an algorithm that uses m queries to 1-STAT and
has success probability 2/3 gives an algorithm that uses m queries to VSTAT(81m) and has success
probability 2/3 − 1/9 = 5/9. For some m = Ω(n2 /k2 ), Theorem 5.4 applied with r = Ω(1) implies
that such algorithm cannot exist. This implies the lower bound for 1-bit sampling algorithms stated
in Theorem 2.10.

5.2

Generalized Planted Densest Subgraph

We will now show lower bounds on detecting a (p, q)-planted densest subgraph, a generalization of
the distributional planted biclique problem we defined in Definition 2.11. Note that p = 1, q = 1/2
is precisely the distributional planted k-biclique problem. For this generalized problem, we will
take D, the reference distribution, to be that of n independent Bernoulli variables with bias q.
Before we give P
our results for this problem, we have to fix some further notation:
for x ∈ {0, 1}n ,
P
1 − xi (the number of
we define kxk1 =
xi (i.e. the number of 1’s in x); similarly for kxk1 =
0’s in x). We will denote the restriction of a set by subscripting so that xS is x restricted to the
subset S ⊆ [n]. We use S̄ to denote the complement of S in the current ground set.
First, we give a computation of the correlation. This is a generalized version of Lemma 5.1.
Lemma 5.5. Fix 0 < q ≤ p ≤ 1 and let ∆pq = 1 +

(p−q)2
q(1−q) .

For i, j ∈ [m],

D
E

 k2
D̂i , D̂j
= ∆λpq − 1 2 ,
n
D
26

where λ = |Si ∩ Sj |.
Proof. For any x, we have D(x) = q kxk1 (1 − q)kxk1 . For Di (x):
Di (x) = Pr[x|planted] Pr[planted] + Pr[x|not planted] Pr[not planted]


k kxSi k
k
xS¯
xS¯
x
k
k
S
i 1 (1 − q)
i 1 +
i 1q
1 (1 − p)
= p
1−
q kxk1 (1 − q)kxk1 .
n
n
For Di (x)/D(x) − 1, we have:
x¯
k pkxSi k1 (1 − p)kxSi k1 q Si 1 (1 − q)
Di (x)
−1= ·
D(x)
n
q kxk1 (1 − q)kxk1

 

k p kxSi k1 1 − p kxSi k1 k
=
− .
n q
1−q
n

xS¯

i 1

−

k
n

Now, for Sj where |Si ∩ Sj | = λ, we want to compute:
D

D̂i , D̂j

E

D

 2
k
=
n

X

#  
" 
kxS k
xSi k 1 
k
i
1
p
p
1−p
−1 
q kxk1 (1 − q)kxk1
q
1
−
q
q
n

x∈{0,1}

xSj

1



1−p
1−q



There are three types of terms in the product in the summand. We deal with all these terms by
repeated applications of the Binomial theorem. The first term illustrates this approach:
X
q kxk1 (1 − q)kxk1 = (q + (1 − q))n = 1.
x∈{0,1}n

The second type of term is given by:
X

x∈{0,1}n

q kxk1 (1 − q)kxk1
X

=

q

x∈{0,1}n

=

X

y∈{0,1}|Si |

xS¯

i 1


 kxS k 
i 1
1 − p kxSi k1
p
q
1−q

(1 − q)

xS¯

i 1

pkyk1 (1 − p)kyk1

pkxSi k1 (1 − p)kxSi k1
X

¯
z∈{0,1}|Si |

pkzk1 (1 − p)kzk1

= 1.
The third type of term is more complicated – using the above trick, we can restrict x to T = Si ∪ Sj
because the sum taken over the remaining xi yields 1.


" 
k x S k #   x S 
 xS
xSi k1 
k
X
j
i
j
1
p
1−p
1−p
1
1

 p
q kxk1 (1 − q)kxk1
q
1
−
q
q
1
−
q
x∈{0,1}n


" 
kxS k #   xS 
 xS
xSi k1 
k
X
i
j
j
1
1−p
1−p
p
1
1
 p
.
=
q kxk1 (1 − q)kxk1
q
1
−
q
q
1
−
q
|T |
x∈{0,1}

27

xSj

1



− 1 .

Similarly, we can sum x over coordinates in Si \ Sj and Sj \ Si . Hence, the sum simplifies:

#  
" 

 xS
xSj
kxSi k1  1 − p kxSi k1
X
j 1
p
1
−
p
p
1


q kxk1 (1 − q)kxk1
q
1−q
q
1−q
n
x∈{0,1}
" 
kxk1 #2
kxk1 
X
p
1
−
p
=
q kxk1 (1 − q)kxk1
q
1−q
S ∩S
x∈{0,1}| i j |
 2 kxk1 
kxk1
X
p
(1 − p)2
=
q
1−q
S ∩S
x∈{0,1}| i j |
 2
λ
p
(1 − p)2
=
+
q
1−q
= ∆λpq .

Combining these three calculations yields:
D

D̂i , D̂j

E

D

 2 

k
∆λpq − 1
=
n

Next, in analogy with Lemma 5.2, we give a bound on average correlation for sufficiently many
distributions.
2

(p−q)
Lemma 5.6. Fix 0 < q < p ≤ 1 and let ∆pq = 1 + q(1−q)
. For δ > 0 and k ≤ n1/2−δ , if n2δ ≥ 8∆pq

then for any integer ℓ ≤ k, S ∈ Sk and A ⊆ Sk of size at least 2(m − 1)/n2ℓδ ,
E

2k2 
1 X D
D̂S , D̂i < 2 ∆ℓpq − 1 .
|A|
n
Si ∈A

Proof. We proceed as in the proof of Lemma 5.2. Recall that Tλ = {Si | |S ∩ Si | = λ} denotes the
subset of all k-subsets that intersect with S in exactly λ indices. Let λ0 be the smallest λ for which
A ∩ Tλ is non-empty. As before, we obtain that λ0 < ℓ.
We now bound the average correlation with D̂S as follows:
X

Si ∈A

k
X

k2
· ∆jpq − 1 |Tj ∩ A|
2
n
j=λ0


k


2
X
k
≤ 2 · |Tλ0 ∩ A| ∆λpq0 − 1 +
|Tj |(∆jpq − 1) .
n

hD̂S , D̂i i ≤

j=λ0 +1

To bound the sum

k
X

j=λ0 +1

(∆jpq − 1) |Tj |
28

it suffices to show that it is geometrically decreasing as:
(∆jpq − 1) |Tj | ≥ 2 · (∆j+1
pq − 1) |Tj+1 | .
We first note that ∆pq > 1 and therefore for j ≥ 1,
∆j+1
pq − 1
∆jpq − 1

≤ ∆pq + 1 < 2∆pq .

From equation (5) in the proof of Lemma 5.2 and our assumption on ∆pq we obtain the necessary
property:
|Tj |
(j + 1)n2δ
2(∆j+1
pq − 1)
≥
≥ 4 · ∆pq >
.
|Tj+1 |
2
∆jpq − 1
To conclude,

X

Si ∈A



k


X
k2 
hD̂S , D̂i i ≤ 2 · |Tλ0 ∩ A| ∆λpq0 − 1 +
|Tj |(∆jpq − 1)
n
j=λ0 +1

k2





λ0 +1
− 1)
≤ 2 · |Tλ0 ∩ A| ∆λpq0 − 1 + 2 · |Tλ0 +1 |(∆pq
n


k2
≤ 2 · 2 · |A| ∆λpq0 +1 − 1
n


k2
≤ 2 · 2 · |A| ∆ℓpq − 1 .
n

From here the bound on statistical dimension SDA of detecting the (p, q)-planted densest subgraph now follows in the same way as in Theorem 5.3.
Theorem 5.7. Fix 0 < q < p ≤ 1. For δ > 0 and k ≤ n1/2−δ let Z be the distributional (p, q)planted densest k-subgraph problem. Then for any ℓ ≤ k,
!
 1
2k2  ℓ
SDA Z, 2 ∆pq − 1 , n ≥ n2ℓδ /2.
n
k

provided that n2δ ≥ 8∆pq .

This SDA bound yields lower bounds for the VSTAT oracle:
(p−q)2
q(1−q) .
VSTAT(n2 /(6k2 (∆ℓpq

Corollary 5.8. Fix 0 < q < p ≤ 1 and let ∆pq = 1 +
n1/2−δ ,

nΩ(ℓ)

For any constant δ > 0, any

k ≤
ℓ ≤ k, at least
queries to
− 1))) are required to solve the
distributional (p, q)-planted densest k-subgraph problem with probability at least 2/3 provided that
n2δ ≥ 8∆pq .

29

Similarly, by Theorem 3.7, the same lower bound applies to the decision version of the problem.
One is often interested in the case when q = 1/2 and p = 1/2 + α (the classical planted densest
2
k-subgraph problem). In this setting ∆pq = 1 + 4α2 and ∆ℓpq − 1 ≤ e4α ℓ − 1 ≤ 8α2 ℓ whenever
ℓ ≤ 1/(4α2 ). This gives a lower bound of nΩ(ℓ) against VSTAT(n2 /(48ℓα2 k2 )) as stated in Corollary
2.12.
Finally, we give an example of a corollary for the 1-STAT oracle.
Corollary 5.9. For constants c, δ > 0, density p = 1/2 + 1/nc , and k ≤ n1/2−δ , Let D be the
uniform distribution over {0, 1}n and D be the set of all (p, 1/2)-planted densest k-subgraph distributions. Any (randomized) 1-bit sampling algorithm that solves the decision problem B(D, D) with
probability at least 2/3, requires Ω((n2+2c )/k2 ) queries to 1-STAT.
Proof. By the argument above with α = 1/nc , SDA(B(D, D), 16k2 ℓ/n2+2c ) ≥ n2ℓδ /2. For ℓ =
4/2δ we obtain that SDA(B(D, D), 64k2 /n2+2c ) ≥ n4 /2. By applying Theorem 3.16 for success
probability 2/3, we obtain a lower bound of

 2+2c 

 4

n
n 49/9 n2+2c
d/3 (4/3 + 1)2
,
,
·
=Ω
.
= min
m = min
2
2
48γ̄
12 48
64k
k2
samples to 1-STAT.

6

Applications to Statistical Query Learning

We will now use Corollary 3.12 to demonstrate that our results generalize the notion of statistical
query dimension in learning theory and the statistical query lower bounds based on SQ-DIM. We
then show that our lower bounds imply stronger and more general lower bounds in the context of
learning.
We start with a few relevant definitions. In an instance of a PAC learning problem, the learner
has access to random examples of an unknown boolean function c : X ′ → {−1, 1} from a set
of Boolean functions C. A random example is a pair including a point and its label (x′ , c(x′ ))
such that x′ is drawn randomly from a distribution D ′ , which might or might not be known to
the learning algorithm (whenever necessary, we use ′ to distinguish variables from the identically
named ones in the context of general search problems). Specifically, for a target function c ∈ C
and distribution D ′ over X ′ we denote by Dc over X = X ′ × {−1, 1}, where Dc (x′ , c(x′ )) = D ′ (x′ )
and Dc (x′ , −c(x′ )) = 0.
For ǫ > 0, the goal of an ǫ-accurate learning algorithm is to find, with high probability, a Boolean
hypothesis h for which Prx′ ∼D′ [h(x′ ) 6= c(x′ )] ≤ ǫ. A statistical query learning algorithm [Kearns,
1998] has access to the STAT oracle for the input distribution Dc in place of random examples.

6.1

Relationship to SQ-DIM

Blum et al. [1994] defined the statistical query dimension or SQ-DIM of a set of functions C and
distribution D ′ over X ′ as follows (we present a simplification and strengthening due to Yang
[2005]).
Definition 6.1 ([Blum et al., 1994]). For a concept class C and distribution D ′ , SQ-DIM(C, D ′ ) =
d′ if d′ is the largest value for which there exist d′ functions c1 , c2 , . . . , cd′ ∈ C such that for every
i 6= j, |hci , cj iD′ | ≤ 1/d′ .
30

We first observe that correlations of Boolean functions relative to a distribution D ′ are equivalent to correlations of corresponding distributions over examples relative to some reference distribution. Namely, let the reference distribution D be the distribution for which for every (x′ , ℓ) ∈ X,
D(x′ , ℓ) = D ′ (x′ )/2. This is the distribution in which points are distributed according to D ′ and
labels are random unbiased coin flips. We denote it by D ′ × {1/2, 1/2}.
Lemma 6.2. For a distribution D ′ and any Boolean functions c, c1 and c2 , For all x′ ∈ X ′ ,
Dc (x′ ,ℓ)
′
D(x′ ,ℓ) − 1 = ℓ · c(x ) and


Dc2
Dc1
− 1,
−1
= hc1 , c2 iD′ .
D
D
D
′
′ ′
Proof. We first note that the definition of D ensures
 that D(x , ℓ) is non-vanishing only when D (x )
Dc
is non-vanishing and hence the function D − 1 is well-defined for any Boolean c ∈ C. For every
c ∈ C, we have

Dc (x′ , c(x′ ))
− 1 = 2 − 1 = 1 and
D(x′ , c(x′ ))
Therefore,


Dc (x′ ,ℓ)
D(x′ ,ℓ)

Dc (x′ , −c(x′ ))
− 1 = 0 − 1 = −1.
D(x′ , −c(x′ ))

− 1 = ℓ · c(x′ ). This implies that for any c1 , c2 ∈ C,


Dc2
Dc1
− 1,
−1
= E [ℓ · c1 (x′ ) · ℓ · c2 (x′ )] = E [c1 (x′ ) · c2 (x′ )] = hc1 , c2 iD′ .
D
D
D′
(x′ ,ℓ)∼D
D

The direct implication of this is that if SQ-DIM(C, D ′ ) = d′ then there exist d′ distributions
over examples that are (1/d′ , 1)-correlated relative to D. In particular, the decision problem of distinguishing example distributions from D has large statistical dimension with pairwise correlations.
We state this formally:
Theorem 6.3. For a concept class C and distribution D ′ over X let d′ = SQ-DIM(C, D ′ ). Then
for DC = {Dc | c ∈ C} and D = D ′ × {1/2, 1/2}, SD(B(DC , D), 1/d′ , 1) ≥ d′ .
Blum et al. [1994] proved that if a class of functions is learnable using only a polynomial number
of statistical queries of inverse polynomial tolerance then its statistical query dimension is polynomial. Yang [2005] strengthened their result and proved the following bound (see [Szörényi, 2009]
for a simpler proof).
Theorem 6.4 ([Yang, 2005]). Let C be a class of functions and D ′ be a distribution over X ′ and
let d′ = SQ-DIM(C, D ′ ). Any SQ algorithm that learns C over D ′ with error ǫ < 1/2 − 1/(2d′1/3 )
requires at least d′1/3 /2 − 1 queries to STAT(1/d′1/3 ).
In this result, the distribution D ′ is fixed and known to the learner (such learning is referred
to as distribution-specific) and it can be used to lower bound the complexity of learning C even in
a weak sense. Specifically, when the learning algorithm is only required to output a hypothesis h′
such that Prx′ ∼D′ [h′ (x′ ) 6= c(x′ )] ≤ 1/2 − γ ′ for some inverse polynomial γ ′ . It is well-known that
weak learning of functions from C implies ability to distinguish examples of any function in C from
points labeled randomly. This implies that we can apply our lower bound for decision problems to
obtain a lower bound for weak learning that is essentially the same as the result of Yang [2005].
31

Corollary 6.5. Let C be a class of functions and D ′ be a distribution over X ′ and let d′ =
SQ-DIM(C, D ′ ). Any SQ algorithm that learns C over D ′ with error ǫ < 1/2 − 1/d′1/3 requires
at least 2d′1/3 − 1 queries to STAT(1/d′1/3 ).
Proof. Let DC = {Dc | c ∈ C} and D = D ′ × {1/2, 1/2}. We convert the weak learning algorithm
into the algorithm for B(DC , D) as follows. Run the weak learning algorithm. Given hypothesis h
estimate the prediction error within d′−1/3 /2 by using the query φ(x′ , ℓ) = h(x′ ) · ℓ with tolerance
d′−1/3 . If the answer to the query is > d′−1/3 output 1 (meaning the input distribution is in
DC ), otherwise output 0 (meaning that the input distribution is D). Note that ED [φ] = 0 and
therefore this algorithm will always output 0 on D. Further, if the input distribution is Dc and
PrD′ [h(x′ ) 6= c(x′ )] < 1/2 − 1/d′1/3 then
E

(x′ ,ℓ)∼Dc

[φ(x′ , ℓ)] =

E

(x′ ,ℓ)∼Dc

[h(x′ ) · ℓ] = E [h(x′ ) · c(x′ )] = 1 − 2 ′Pr ′ [h(x′ ) 6= c(x′ )] > 2/d′1/3 .
′
′
x ∼D

x ∼D

Therefore in this case the answer to the query will be > 2/d′1/3 −1/d′1/3 = 1/d′1/3 and the algorithm
will output 1.
By Theorem 6.3, SD(B(DC , D), 1/d′ , 1) ≥ d′ . We can now apply the lower bound in Corollary
3.12 with γ ′ = d′−2/3 /2 to obtain that our algorithm must use 2d′1/3 queries to STAT(d′−1/3 ) to
solve the problem. Our algorithm used one more query than the learning algorithm (of the same
tolerance) which gives the stated lower bound.
This corollary implies that lower bounds based on SQ-DIM are a special case of our lower
bounds. One can also similarly show that the lower bounds based on the statistical query dimension
of Feldman [2012] that characterizes learning to high accuracy are also a special case of our lower
bounds.

6.2

Lower Bounds for 1-bit Sampling Oracle

We now show how our results can be used to obtain lower bounds against 1-bit sampling algorithms based on SQ-DIM. Such lower bounds have been previously proved by Yang [2005] who
referred to his model as Honest SQ model (apparently unaware of the connection to the model in
[Ben-David and Dichterman, 1998]). In the Honest SQ model, the learner has access to an HSQ
oracle. A query to HSQ oracle is a function φ : X ′ × {−1, 1}P
→ {−1, 1} and a sample size t > 0.
1
′
′
′
The oracle draws x1 , . . . , xt ∼ D , and returns the value t ti=1 φ(x′ , c(x′ )). The total sample
complexity of an algorithm is the sum of the sample sizes it passes to HSQ.
We note that using 1-STAT is equivalent to a call to HSQ with sample size 1. Also 1-STAT
can simulate estimation of queries from a larger number of samples in a straightforward way while
obtaining the same total sample complexity.
Therefore HSQ is equivalent to the 1-STAT oracle.
√
′
′
Using Lemma 3.10 with γ = 1/ d to convert a bound on√pairwise correlations
√ to a bound
on average correlation, we can obtain that SDA(B(DC , D), 1/ d′ + 1/d′ , 1) ≥ d′ /(1 − 1/d′ ).
Plugging this bound into Theorem 3.16, we can derive sample complexity bounds on 1-bit sampling
algorithms for learning in the same way as in the proof of Corollary 6.5.
Corollary 6.6. Let C be a class of functions, D ′ be a distribution over X ′ , d′ = SQ-DIM(C, D ′ ) and
ǫ = 1/2− 1/d′1/4 . Then any 1-bit
√ sampling algorithm that, with probability at least 2/3, ǫ-accurately
learns C over D ′ requires Ω( d′ ) queries to 1-STAT.
32

This lower bound is similar to the result of Yang [2005] who shows a bound of Ω(d′ / log d′ )
using a stronger 1/d′3 upper bound on correlations (and a substantially more involved proof). Note
that the inverse of the maximum pairwise correlation is usually much lower than the number of
functions. Therefore our result will give a stronger lower bound in most cases.

6.3

New Lower Bound for Learning

We now briefly describe a version of our lower bound for weak distribution-specific learning. It
is stronger than known SQ-DIM-based bounds in several ways. First, it explicitly decouples the
tolerance (or number of samples) from the number of queries. This is particularly relevant for
attribute-efficient learning that is learning when the dimension is high but the target function
depends on few variables (see [Feldman, 2014] for more details on SQ learning in this setting).
Second, it captures sample complexity in a tighter way by going to average correlations and proving
lower bounds against VSTAT. Lower bounds against VSTAT also imply tighter lower bounds for
1-STAT and, via the reductions in [Feldman et al., 2013], against stronger oracles.
We now give versions of our main definitions specialized to the case of distribution-specific PAC
learning. Although the target distribution is fixed, by varying the concept by which examples
are labeled, we effectively generate a large set of different distributions as before. The average
correlation can be defined directly for a set of functions C ′ relative to a distribution D ′ :
X
. 1
|hc1 , c2 iD′ | .
ρ(C ′ , D ′ ) = ′ 2
|C |
′
c1 ,c2 ∈C

Definition 6.7. For γ̄ > 0, a distribution D ′ over domain X ′ and a set of Boolean functions C
over X ′ the statistical dimension of C over D ′ with average correlation γ̄ is defined to be the
largest integer d for which there exists a finite set of functions Cγ̄ ⊆ C such that for any subset
C ′ ⊆ Cγ̄ , where |C ′ | ≥ Cγ̄ /d, ρ(C ′ , D ′ ) ≤ γ̄. We denote it by SDA(C, D ′ , γ̄).
Using Theorem 3.7 and the reduction in Corollary 6.5 imply Theorem 2.8.

Acknowledgments
We thank Benny Applebaum, Avrim Blum, Uri Feige, Ravi Kannan, Michael Kearns, Robi Krauthgamer,
Moni Naor, Jan Vondrak, and Avi Wigderson for insightful comments and helpful discussions.

References
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie. Testing k-wise and almost
k-wise independence. In STOC, pages 496–505, 2007.
Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random
graph. In SODA, pages 594–598, 1998.
Brendan P. W. Ames and Stephen A. Vavasis. Nuclear norm minimization for the planted clique
and biclique problems. Math. Program., 129(1):69–89, 2011.
Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In STOC, pages 171–180, 2010.
33

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Computational complexity and
information asymmetry in financial products (extended abstract). In ICS, pages 49–65, 2010.
P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural
results. Journal of Machine Learning Research, 3:463–482, 2002.
Alexandre Belloni, Robert M. Freund, and Santosh Vempala. An efficient rescaled perceptron
algorithm for conic systems. Math. Oper. Res., 34(3):621–641, 2009.
Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. J. Comput. Syst.
Sci., 56(3):277–298, 1998.
Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal
component detection. In COLT, pages 1046–1066, 2013.
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan.
Detecting high log-densities: an o(n1/4 ) approximation for densest k-subgraph. In STOC, pages
201–210, 2010.
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan
Zhou. Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In SODA,
pages 388–405, 2012.
A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the SuLQ framework. In
PODS, pages 128–138, 2005.
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven
Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis.
In STOC, pages 253–262, 1994.
Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh Vempala. A polynomial-time algorithm
for learning noisy linear threshold functions. Algorithmica, 22(1/2):35–52, 1998.
Guy Bresler, David Gamarnik, and Devavrat Shah. Structure learning of antiferromagnetic ising
models. In NIPS, pages 2852–2860, 2014.
S. Brubaker and S. Vempala. Random tensors and planted cliques. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 5687, pages 406–419.
2009.
T. T. Cai, T. Liang, and A. Rakhlin. Computational and Statistical Boundaries for Submatrix
Localization in a Large Noisy Matrix. ArXiv e-prints, February 2015.
C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Ng, and K. Olukotun. Map-reduce for machine
learning on multicore. In NIPS, pages 281–288, 2006.
Amin Coja-Oghlan. Graph partitioning via adaptive spectral techniques. Combinatorics, Probability & Computing, 19(2):227–284, 2010.
Y. Dekel, O. Gurel-Gurevich, and Y. Peres. Finding hidden cliques in linear time with high probability. In ANALCO, pages 67–75, 2011.
34

A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the
em algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977.
Yash Deshpande and Andrea Montanari. Finding hidden cliques of size \sqrt{N/e} in nearly linear
time. CoRR, abs/1304.7047, 2013.
Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems.
In COLT, pages 523–562, 2015.
URL
http://jmlr.org/proceedings/papers/v40/Deshpande15.html.
Shaddin Dughmi. On the hardness of signaling. In FOCS, pages 354–363, 2014.
John Dunagan and Santosh Vempala. A simple polynomial-time rescaling algorithm for solving
linear programs. Math. Program., 114(1):101–114, 2008.
U. Feige and R. Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms, 16(2):195–208, 2000.
U. Feige and D. Ron. Finding hidden cliques in linear time. In AofA, pages 189–204, 2010.
Uriel Feige. Relations between average case complexity and approximation complexity. In IEEE
Conference on Computational Complexity, page 5, 2002.
Uriel Feige and Robert Krauthgamer. The probable value of the Lovász–Schrijver relaxations for
maximum independent set. SICOMP, 32(2):345–370, 2003.
V. Feldman. Evolvability from learning algorithms. In STOC, pages 619–628, 2008.
V. Feldman. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer System Sciences, 78(5):1444–1459, 2012.
Vitaly Feldman. Open problem: The statistical query complexity of learning sparse halfspaces. In
COLT, pages 1283–1289, 2014.
Vitaly Feldman.
A general characterization of the statistical query complexity.
abs/1608.02198, 2016. URL http://arxiv.org/abs/1608.02198.

CoRR,

Vitaly Feldman, Will Perkins, and Santosh Vempala. On the complexity of random satisfiability
problems with planted solutions. CoRR, abs/1311.4821, 2013. Extended abstract in STOC 2015.
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala.
Statistical query algorithms for stochastic convex optimization.
CoRR, abs/1512.09170, 2015.
URL
http://arxiv.org/abs/1512.09170.
Alan M. Frieze and Ravi Kannan. A new approach to the planted clique problem. In FSTTCS,
pages 187–198, 2008.
C. Gao, Z. Ma, and H. H. Zhou. Sparse CCA: Adaptive Estimation and Computational Barriers.
ArXiv e-prints, September 2014.
A. E. Gelfand and A. F. M. Smith. Sampling based approaches to calculating marginal densities.
Journal of the American Statistical Association, 85:398–409, 1990.
35

Bruce E. Hajek, Yihong Wu, and Jiaming Xu.
Computational lower bounds for
community detection on random graphs.
In COLT, pages 899–928, 2015.
URL
http://jmlr.org/proceedings/papers/v40/Hajek15.html.
Johan Håstad. Some optimal inapproximability results. J. ACM, 48:798–859, July 2001. ISSN
0004-5411.
W. K. Hastings. Monte carlo sampling methods using markov chains and their applications.
Biometrika, 57(1):97–109, 1970.
Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best nash equilibrium?
SIAM J. Comput., 40(1):79–91, 2011.
Mark Jerrum. Large cliques elude the metropolis process. Random Struct. Algorithms, 3(4):347–
360, 1992.
Ari Juels and Marcus Peinado. Hiding cliques for cryptographic security. Des. Codes Cryptography,
20(3):269–280, 2000.
Ravi Kannan. personal communication.
R. Karp. Probabilistic analysis of graph-theoretic algorithms. In Proceedings of Computer Science
and Statistics 12th Annual Symposium on the Interface, page 173, 1979.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam
Smith. What can we learn privately? SIAM J. Comput., 40(3):793–826, June 2011.
M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):
983–1006, 1998.
Subhash Khot. Ruling out ptas for graph min-bisection, densest subgraph and bipartite clique. In
FOCS, pages 136–145, 2004.
Scott Kirkpatrick, D. Gelatt Jr., and Mario P. Vecchi. Optimization by simmulated annealing.
Science, 220(4598):671–680, 1983.
Ludek Kucera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics,
57(2-3):193–212, 1995.
Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection. CoRR,
abs/1309.5914, 2013. URL http://arxiv.org/abs/1309.5914.
F. McSherry. Spectral partitioning of random graphs. In FOCS, pages 529–537, 2001.
R. Meka, A. Potechin, and A. Wigderson. Sum-of-squares lower bounds for planted clique. In
STOC, pages 87–96, 2015.
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and
Edward Teller. Equations of state calculations by fast computing machines. Journal of Chemical
Physics, 21:1087–1092, 1953.

36

L. Minder and D. Vilenchik. Small clique detection and approximate nash equilibria. 5687:673–685,
2009.
K. Pearson. On the criterion that a given system of deviations from the probable in the case of
a correlated system of variables is such that it can be reasonably supposed to have arisen from
random sampling. Philosophical Magazine, Series 5, 50(302):157–175, 1900.
Bart Selman, Henry Kautz, and Bram Cohen. Local search strategies for satisfiability testing.
In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 521–532,
1995.
R. Servedio. Computational sample complexity and attribute-efficient learning. Journal of Computer and System Sciences, 60(1):161–178, 2000.
J. Steinhardt, G. Valiant, and S. Wager. Memory, communication, and statistical queries. In COLT,
pages 1490–1516, 2016.
Jacob Steinhardt and John C. Duchi.
Minimax rates for memory-bounded
sparse linear regression.
In COLT, pages 1564–1587,
2015.
URL
http://jmlr.org/proceedings/papers/v40/Steinhardt15.html.
Balázs Szörényi. Characterizing statistical query learning: Simplified notions and proofs. In ALT,
pages 186–200, 2009.
M Tanner and W Wong. The calculation of posterior distributions by data augmentation (with
discussion). Journal of the American Statistical Association, 82:528–550, 1987.
Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to
their probabilities. Theory of Probab. and its Applications, 16(2):264–280, 1971.
V. Černý. Thermodynamical approach to the traveling salesman problem: An efficient simulation
algorithm. Journal of Optimization Theory and Applications, 45(1):41–51, January 1985. ISSN
0022-3239.
T. Wang, Q. Berthet, and R. J. Samworth. Statistical and computational trade-offs in estimation
of sparse principal components. ArXiv e-prints, August 2014.
Ke Yang. On learning correlated boolean functions using statistical queries. In ALT, pages 59–76,
2001.
Ke Yang. New lower bounds for statistical query learning. J. Comput. Syst. Sci., 70(4):485–509,
2005.
Andrew Yao. Probabilistic computations: Toward a unified measure of complexity. In FOCS, pages
222–227, 1977.

Yuchen Zhang,
John C. Duchi,
Michael I. Jordan,
and Martin J. Wainwright.
Information-theoretic lower bounds for distributed statistical estimation with communication constraints.
In NIPS, pages 2328–2336, 2013.
URL
http://papers.nips.cc/paper/4902-information-theoretic-lower-bounds-for-distributed-statisti

37

A

Average-case vs Distributional Planted Bipartite Clique

In this section we show the equivalence between the average-case planted biclique problem (where
a single graph is chosen randomly) and the distributional biclique problem (where a bipartite graph
is obtained from independent samples over {0, 1}n ). The primary issue is that in the distributional
biclique problem the biclique does not necessarily have the same size on the left side of vertices as
it does on the right side. We show that this is easy to fix by producing planted bicliques of smaller
size on one of the sides. We do this by replacing vertices of the graph with randomly connected
ones. We now describe the reductions more formally.
Definition A.1. [Average-case planted biclique APBC(n, k1 , k2 )] Given integers 1 ≤ k1 , k2 ≤ n,
consider the following distribution Davg (n, k1 , k2 ) on bipartite graphs on [n] × [n] vertices. Pick two
random sets of k1 and k2 vertices each from left and right side, respectively, say S1 and S2 . Plant a
bipartite clique on S1 × S2 and add an edge between all other pairs of vertices with probability 1/2.
The problem is to recover S1 and S2 given a random graph sampled from Davg (n, k1 , k2 ).
We will refer to the distributional biclique problem with n samples as DPBC(n, k). Recall that
in this problem we are given n random and independent samples from distribution DS over {0, 1}n
for some unknown S ⊂ [n] of size k (see Definition 1.1). The goal is to recover S.
Theorem A.2. Suppose that there is an algorithm that solves APBC(n, k′ , k′ ) in time T ′ (n, k′ )
and outputs the correct answer with probability p′ (n, k′ ). Then there exists an algorithm that solves
DPBC(n, k) in time T (n, k) = O(nkT ′ (n, k/2)) and outputs the correct answer with probability
p(n, k) = p′ (n, k/2) − n2−Ω(k) .
Proof. We will think of the distribution Davg (n, k′ , k′ ) on graphs as a distribution on their respective adjacency matrices from {0, 1}n×n . Let A(n, k′ ) be the algorithm that solves an instance of
APBC(n, k′ , k′ ). Given k and n, and access to n samples from DS for some set S of size k, we will
design an algorithm that finds S by making O(nk) calls to the algorithm A(n, k′ ) that solves an
instance of APBC(n, k′ , k′ ).
Let M be the n × n binary matrix whose rows are the n samples from DS . First apply a random
permutation π : [n] → [n] to the columns of M to obtain M ′ (this will ensure that the planted set
is uniformly distributed among the n coordinates, which is necessary in order to obtain instances
distributed according to Davg (n, k′ , k′ )).
In what follows we will denote by k′ × k a biclique with k′ vertices on the left and k vertices
on the right. Note that M ′ has a k′ × k planted biclique for some k′ that is distributed according
to the binomial distribution B(n, k/n). We denote the vertices on the left side of this biclique by
L. By a multiplicative Chernoff bound, Pr[k/2 ≤ k′ ≤ 2k] ≥ 1 − 2e−k/8 . From now on we will
condition on this event occurring.
We first suppose that k ≤ k′ ≤ 2k. We aim at obtaining instances of APBC(n, k, k) but recall
that the left side of the planted bliclique has size k′ ≥ k. To reduce the size of the left side of
the planted biclique to k we will be replacing the vertices on the left side by randomly connected
′ , we choose a
ones, one-by-one in a random order. That is, start with M0′ = M ′ . To obtain Mt+1
random and uniform row of Mt′ that was not previously picked and replace it with a random and
uniform {0, 1}n vector. This gives a sequence of random matrices: M1′ , M2′ , . . . , Mn′ . Clearly, M0′
has a planted biclique of size k′ × k and Mn′ does not have a planted biclique (or, equivalently,
has a 0 × k biclique). A single step reduces the size of the left side of the biclique by at most 1.
38

Therefore for some i∗ , Mi′∗ has a k × k biclique. We denote the left side of this biclique by L∗ . It
is also easy to see that for every step i, conditioned on Mi′ containing k′′ out of vertices in L, Mi′
is distributed exactly according to Davg (n, k′′ , k). We now condition on the event that for all i, Mi′
does not contain a k × k biclique such that its right side is different from π(S). It is not hard to
see that this event happens with probability at least 1 − n2−Ω(k) .
To recover S, we run A(n, k) on all the matrices Mi′ . Let Li × Si be the biclique that A outputs
on Mi′ . We verify that Li × Si is a k × k biclique in Mi′ . If so we output π −1 (Si ). Note that when
executed on Mi′∗ , with probability p′ (n, k) this procedure will return L∗ × π(S). In this case we
will return exactly S. Further, by our conditioning, if the output of A is a k × k biclique then its
right side must be π(S).
We can now assume that k/2 ≤ k′ < k. We aim at obtaining instances of APBC(n, k′ , k′ ). To
achieve this we reduce the size of the right side of the planted biclique to k′ in the same way as
we reduced the size of the left side above: we will be replacing the vertices on the right side by
randomly connected ones, one-by-one in a random order. As before we start with M0′ = M ′ . To
′ , we choose a random and uniform column of M ′ that was not previously picked and
obtain Mt+1
t
replace it with a random and uniform {0, 1}n vector. This gives a sequence of random matrices:
M1′ , M2′ , . . . , Mn′ . We know that for some i∗ , Mi′∗ has a k′ × k′ biclique. We denote the right side
of this biclique by S ∗ . We now condition on the event that for all i, Mi′ does not contain a k′ × k′
biclique such that its left side is different from L. It is not hard to see that this event happens with
′
probability at least 1 − n2−Ω(k ) = 1 − n2−Ω(k) .
Assume for now that we know k′ . To recover S, we run A(n, k′ ) on all the matrices Mi′ . Let
Li × Si be the biclique that A outputs on Mi′ . We verify that Li × Si is a k′ × k′ biclique in Mi′ .
If so we let S ′ be the set of all vertices on the right side connected to each vertex in Li (in the
original graph after the permutation). If |S ′ | = k, we output π −1 (S ′ ). Note that when executed on
′ , with probability p′ (n, k ′ ), this procedure will return L × S ∗ . Further, by our conditioning if
Mi∗
the output of A is a k′ × k′ biclique then its left side must be L. All vertices in π(S) are connected
to L. The probability that any other vertex on the right side of M ′ is connected to all vertices in
L is at most n · 2−k . Hence, conditioned on this event not occurring, we will recover exactly S.
To address the fact that k′ is not known, for each value of k1 = k − 1, k − 2, . . . , k/2, we run
the algorithm under the assumption that k′ = k1 and stop once the algorithm has found a k′ × k′
biclique. If k1 > k ′ then, by our conditioning on none of Mi′ containing a k′ × k′ biclique such that
its left side is different from L there cannot exist a k1 × k1 biclique in the graph. Therefore the
algorithm will not output anything until k1 = k′ at which point our analysis above applies.
To analyze the success probability and running time we can assume for simplicity that it is harder
to find smaller planted bicliques than larger ones, and so for k1 ∈ [k/2, k], T ′ (n, k1 ) ≤ T ′ (n, k/2) and
p′ (n, k′ ) ≤ p′ (n, k/2). Therefore the running time of our algorithm is T (n, k) = O(nkT ′ (n, k/2)),
and its success probability is p(n, k) = p′ (n, k/2) − n2−Ω(k) .
We now prove the converse of Theorem A.2.
Theorem A.3. Suppose that there is an algorithm that solves DPBC(n, k) that runs in time
T (n, k) and outputs the correct answer with probability p(n, k). Then there exists an algorithm that
solves APBC(n, k′ , k′ ) in time T ′ (n, k′ ) = O(nk′ T (n, k′ /2)) and outputs the planted biclique with
′
probability p′ (n, k′ ) ≥ p(n, k ′ /2) − n2Ω(−k ) .
Proof. Let A(n, k) denote the algorithm for solving DPBC(n, k), which, for any S ⊆ [n] of size k,
takes n samples chosen according to DS and outputs the planted set S with probability p(n, k). We
39

will construct an algorithm for APBC(n, k′ , k′ ) that takes as input an adjacency matrix M chosen
randomly according to Davg (n, k′ , k′ ), (as in Definition A.1) and outputs a biclique S1 × S2 of size
′
k′ × k′ . Note that, with probability 1 − n2−Ω(k ) , the set S1 × S2 is the unique k′ × k′ biclique in
M and we will condition on this event.
We first observe that an instance of DPBC(n, k) can be equivalently thought of as follows:
first pick an arbitrary set S of k vertices on the right side of the graph; then pick ℓ according
to B(n, k/n); pick a random subset S ′ of ℓ vertices on the left side of the graph; make S ′ × S a
biclique and connect all the other pairs of vertices randomly and independently with probability
1/2. The probability that ℓ ∈ [5k/6, 6k/5] is at least 1 − 2−Ω(k) and therefore the probability that
A(n, k) succeeds conditioned on this event is at least p(n, k) − 2−Ω(k) . This implies that there exists
ℓk ∈ [5k/6, 6k/5] such that conditioned on ℓ = ℓk , the probability that A(n, k) succeeds is at least
p(n, k) − 2−Ω(k) (we note that ℓk might depend on S).
Let M be the adjacency matrix of the given instance of APBC(n, k′ , k′ ). For each column of
M (corresponding to a vertex on the right side), with probability 3/4 we replace it with a random
and uniform vector from {0, 1}n and let M ′ denote the obtained adjacency matrix. We denote by
S the subset of S2 containing vertices that were not replaced by randomly connected vertices. Let
k = |S|. With probability at least 1 − 2−Ω(k) , k ∈ [3k′ /5, 5k′ /6] and we will condition on this event.
We aim at obtaining an instance of DPBC(n, k) in which exactly ℓk vertices on the left are
connected to all vertices in the planted set S. By the argument above, we know that we can assume
that ℓk ∈ [5k/6, 6k/5] ⊆ [k′ /2, k′ ] and A succeeds with probability at least p(n, k) − 2−Ω(k) given
an instance in which exactly ℓk vertices on the left are connected to all vertices in S.
M ′ has a k′ ×k biclique so to reduce the size of the left side of the planted biclique to ℓk we will be
replacing the vertices on the left side by randomly connected ones, one-by-one in a random order as
in the proof of Theorem A.2. This gives a sequence of random matrices: M ′ = M0′ , M1′ , M2′ , . . . , Mn′ .
For every i, Let Si′ denote the subset of vertices in S1 that were not replaced by a randomly
connected vertex in Mi′ . It is also easy to see that for every i, conditioned on |Si′ | = k′′ , Mi′ is
distributed exactly as n samples from DS in which k′′ samples were chosen to be connected to all
vertices in S.
To recover S1 and S2 , we run A(n, k) on all the matrices Mi′ (where, we assume for now that k
is known). Let Li × Ri be the biclique that A outputs on Mi′ . Let S1∗ be the set of all (left side)
vertices connected in the original input graph to all vertices in Ri and S2∗ be the set of all (right
side) vertices in the input graph connected to all vertices in S1∗ . If |S1∗ | = |S2∗ | = k′ then we output
the biclique S1∗ × S2∗ . Otherwise we go to the next step (if none of the steps produces a biclique
the algorithm fails). We first note that, unless the algorithm fails, it outputs a k′ × k′ biclique in
the input graph which, by our conditioning, can only be the true planted biclique. Further, there
exists i∗ such that |Si′∗ | = ℓk . Mi′∗ is distributed as n samples from DS in which ℓk samples were
chosen to be connected to all vertices in S. Therefore by our conditioning, with probability at
least p(n, k) − 2−Ω(k) , A(n, k) will output S. The vertices in S1 are connected to all vertices in S
and with probability at least 1 − n2−k no other vertex in the original graph is. The vertices in
S2 are connected to all vertices in S1 and, by our conditioning no other vertex is. Therefore, with
probability at least p(n, k) − n2−Ω(k) the algorithm will produce the true k ′ × k′ biclique.
To address the fact that k is not known, for each value of k1 = ⌈5k′ /6⌉, . . . , ⌊2k′ /3⌋, we run
the algorithm under the assumption that k = k1 and stop once the algorithm has found a k′ × k′
biclique. The algorithm can only output the true planted biclique and therefore this will not reduce
the success probability.

40

As before, to analyze the success probability and running time we assume for simplicity that it
is harder to find smaller planted sets than larger ones, and so for k1 ∈ [⌊2k′ /3⌋, ⌈5k′ /6⌉], T (n, k1 ) ≤
T (n, k′ /2) and p(n, k) ≤ p(n, k ′ /2). Therefore the running time of our algorithm is T ′ (n, k′ ) =
′
O(nk′ T (n, k′ /2)), and its success probability is p′ (n, k′ ) ≥ p(n, k′ /2) − n2−Ω(k ) .

41

