The Orthogonal Vectors Conjecture
for Branching Programs and Formulas

arXiv:1709.05294v1 [cs.CC] 15 Sep 2017

Daniel Kane
UCSD

Ryan Williams∗
MIT

Abstract
In the O RTHOGONAL V ECTORS (OV) problem, we wish to determine if there is an orthogonal pair
of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires
n2−o(1) time to solve, for all d = ω(log n). Assuming the OVC, optimal time lower bounds have been
proved for many prominent problems in P, such as Edit Distance, Frechet Distance, Longest Common
Subsequence, and approximating the diameter of a graph.
We prove that OVC is true in several computational models of interest:
• For all sufficiently large n and d, OV for n vectors in {0, 1}d has branching program complexity
Θ̃(n · min(n, 2d )). In particular, the lower bounds match the upper bounds up to polylog factors.
• OV has Boolean formula complexity Θ̃(n · min(n, 2d )), over all complete bases of O(1) fan-in.
• OV requires Θ̃(n · min(n, 2d )) wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in.
Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function
in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC,
such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which
have very succinct reductions to OV.
The proofs use a certain kind of input restriction that is different from typical random restrictions
where variables are assigned independently. We give a sense in which independent random restrictions
cannot be used to show hardness, in that OVC is false in the “average case” even for AC0 formulas:
• For every fixed p ∈ (0, 1) there is an εp > 0 such that for every n and d, OV instances where
input bits are independently set to 1 with probability p (and 0 otherwise) can be solved with AC0
formulas of size O(n2−εp ), on all but a on (1) fraction of instances. Moreover, εp → 1 as p → 1.

∗

Supported by an NSF CAREER.

1 Introduction
We investigate the following basic combinatorial problem:
O RTHOGONAL V ECTORS (OV)
Given: n vectors v1 , . . . , vn ∈ {0, 1}d
Decide: Are there i, j such that hvi , vj i = 0?
An instructive way of viewing the OV problem is that we have a collection of n sets over [d], and wish to
find two disjoint sets among them. The obvious algorithm runs in time O(n2 · d), and log(n) factors can be
shaved [Pri99]. For d < log2 (n), stronger improvements are possible: there are folklore O(n · 2d · d)-time
and Õ(n + 2d )-time algorithms (for a reference, see [CST17]). Truly subquadratic-time algorithms have
recently been developed for even larger dimensionalities: the best known result in this direction is that for
all constants c ≥ 1, OV with d = c log n dimensions can be solved in n2−1/O(log c) time [AWY15, CW16].
However, it seems inherent that, as the vector dimension d increases significantly beyond log n, the time
complexity of OV approaches the trivial n2 bound.
Over the last several years, a significant body of work has been devoted to understanding the following
plausible lower bound conjecture:
Conjecture 1.1 (Orthogonal Vectors Conjecture (OVC) [Wil04, AVW14, BI15, ABV15]). For every ε > 0,
there is a c ≥ 1 such that OV cannot be solved in n2−ε time on instances with d = c log n.
In other words, OVC states that OV requires n2−o(1) time on instances of dimension ω(log n). The
popular Strong Exponential Time Hypothesis [IP01, CIP09] (on the time complexity of CNF-SAT) implies OVC [Wil04]. For this reason, and the fact that the OV problem is very simple to work with,
the OVC has been the engine under the hood of many recent conditional lower bounds on classic problems solvable within P. For example, the OVC implies nearly-quadratic time lower bounds for Edit Distance [BI15], approximating the diameter of a graph [RV13], Frechet Distance [Bri14, BM16], Longest
Common Substring and Local Alignment [AVW14], Regular Expression Matching [BI16], Longest Common Subsquence, Dynamic Time Warping, and other string similarity measures [ABV15, BK15], Subtree Isomorphism and Largest Common Subtree [ABH+ 16], Curve Simplification [BBK+ 16], intersection
emptiness of two finite automata [Weh16], first-order properties on sparse finite structures [GIKW17] as well
as average-case hardness for quadratic-time [BRSV17]. Other works surrounding the OVC (or assuming it)
include [WY14, Wil16, AVW16, CDHL16, APRS16, ED16, IR16, CGR16, KPS17].
Therefore it is of strong interest to prove the OVC in reasonable computational models. Note that OV can
be naturally expressed as a depth-three formula with unbounded fan-in: an OR of n2 NORs of d ANDs on
two input variables: an AC0 formula of size O(n2 · d). Are there smaller formulas for OV?

1.1 OVC is True in Restricted Models
In this paper, we study how well OV can be solved in the Boolean formula and branching program models.
Among the aforementioned OV algorithms, only the first two seem to be efficiently implementable by
formulas and branching programs: for example, there are DeMorgan formulas for OV of size only O(n2 d)
and size O(nd2d ), respectively (see Proposition 1).
1

The other algorithms do not seem to be implementable in small space, in particular with small-size
branching programs. Our first theorem shows that the simple constructions solving OV with O(n2 · d)
and O(n · 2d · d) work are essentially optimal for all choices of d and n:
Theorem 1.1 (OVC For Formulas of Bounded Fan-in). For every constant c ≥ 1, OV on n vectors in d dimensions does not have c-fan-in formulas of size O(min{n2 /(log d), n·2d /(d1/2 log d)}), for all sufficiently
large n, d.
Theorem 1.2 (OVC For Branching Programs). OV on n vectors in d dimensions does not have branching
programs of size O(min{n2 , n · 2d /(d1/2 )}/(log(nd) log(d))), for all sufficiently large n, d.
As far as we know, size-s formulas of constant fan-in may be more powerful than size-s branching programs (but note that DeMorgan formulas can be efficiently simulated with branching programs). Thus
the two
√ lower bounds are incomparable. These lower bounds are tight up to the (negligible) factor of
min{ log n, d1/2 } log(d) log(nd), as the following simple construction shows:
Proposition 1. OV has AC0 formulas (and branching programs) of size O(dn · min(n, 2d )).

Proof. The O(dn2 ) bound is obvious: take an OR over all n2 pairs of vectors, and use an AND ◦ OR of
O(d) size to determine orthogonality of the pair. For the O(dn2d ) bound, our strategy is to try all 2d vectors
v, and look for a v that is equal to one input vector and is orthogonal to another input vector. To this end,
take an OR over all 2d possible vectors w over [d], and take the AND of two conditions:
1. There is a vector v in the input such that v = w. This can be computed with an an OR over all n
vectors of an O(d)-size formula, in O(nd) size.
2. There is a vector u in the input such that hu, wi = 0. This can be computed with a parallel OR over
all n vectors of an O(d)-size formula, in O(nd) size.
Note that the above formulas have constant-depth, with unbounded fan-in AND and OR gates. Since DeMorgan formulas of size s can be simulated by branching programs of size O(s), the proof is complete.1
Formulas with symmetric gates. As mentioned above, OV can be naturally expressed as a depth-three
formula of unbounded fan-in: an AC03 formula of O(n2 d) wires. We show that this wire bound is also
nearly optimal, even when we allow arbitrary symmetric Boolean functions as gates. Note this circuit model
subsumes both AC (made up of AND, OR, and NOT gates) and TC (made up of MAJORITY and NOT
gates).
Theorem 1.3. Every formula computing OV composed of arbitrary symmetric functions with unbounded
fan-in needs at least Ω(min{n2 /(log d), n · 2d /(d1/2 log d)}) wires, for all n and d.

1.2 Lower Bounds for Batch Partial Match, Batch Subset Query, Batch Hamming Nearest
Neighbors, etc.
A primary reason for studying OV is its ubiquity as a “bottleneck” special case of many other basic search
problems. In particular, many problems have very succinct reductions from OV to them, and our lower
bounds extend to these problems.
1

This should be folklore, but we couldn’t find a reference; see the Appendix B.

2

We say that a linear projection reduction from a problem A to problem B is a circuit family {Cn } where
each Cn has n input and O(n) outputs, each output of Cn depends on at most one input, and x ∈ A if and
only if C|x| (x) ∈ B, for all possible inputs x. Under this constrained reduction notion, it is easy to see that
if OV has a linear projection reduction to B, then size lower bounds for OV (even in our restricted settings)
imply analogous lower bounds for B as well. Via simple linear projection reductions which preserve both n
and d (up to constant multiplicative factors), analogous lower bounds hold for many other problems which
have been commonly studied, such as:
BATCH PARTIAL M ATCH
Given: n “database” vectors v1 , . . . , vn ∈ {0, 1}d and n queries q1 , . . . , qn ∈ {0, 1, ⋆}d
Decide: Are there i, j such that vi is a partial match of qj , i.e. for all k, qj [k] ∈ {vi [k], ⋆}?
BATCH S UBSET Q UERY
Given: n sets S1 , . . . , Sn ⊆ [d] and n queries T1 , . . . , Tn ⊆ [d]
Decide: Are there i, j such that Si ⊆ Tj ?
BATCH H AMMING N EAREST N EIGHBORS
Given: n points p1 , . . . , pn ∈ {0, 1}d and n queries q1 , . . . , qn ∈ {0, 1}d , integer k
Decide: Are there i, j such that pi and qj differ in at most k positions?

1.3 “Average-Case” OVC is False, Even for AC0
The method of proof in the above lower bounds is an input restriction method that does not assign variables
independently (to 0, 1, or ⋆) at random. (Our restriction method could be viewed as a random process, just
not one that assigns variables independently.) Does OV become easier under natural product distributions of
instances, e.g., with each bit of each vector being an independent random variable? Somewhat surprisingly,
we show that a reasonable parameterization of average-case OVC is false, even for AC0 formulas.
For p ∈ (0, 1), and for a given n and d, we call OV(p)n,d the distribution of OV instances where all bits
of the n vectors are chosen independently, set to 1 with probability p and 0 otherwise. We would like to
understand when OV(p) can be efficiently solved on almost all instances (i.e., with probability 1 − o(1)).
We give formulas of truly sub-quadratic size for every p > 0:
Theorem 1.4. For every p ∈ (0, 1), and every n and d, there is an AC0 formula of size n2−εp that correctly
answers all but a on (1) fraction of OV(p)n,d instances on n vectors and d dimensions, for an εp > 0 such
that εp → 1 as p → 1.
Interestingly, our AC0 formulas have one-sided error, even in the worst case: if there is no orthogonal pair
in the instance, our formulas always output 0. However, they may falsely report that there is no orthogonal
pair, but this only occurs with probability o(1) on a random OV(p)n,d instance, for any n and d.

1.4 Intuition
Our lower bounds give some insight into what makes OV hard to solve. There are two main ideas:
3

1. OV instances with n d-dimensional vectors can encode difficult Boolean functions on d inuts, requiring circuits of size Ω̃(min(2d , n)). This can be accomplished by encoding those strings with “middle”
Hamming weight from the truth table of a hard function with the vectors in an OV instance, in such
a way that finding an orthogonal pair is equivalent to evaluating the hard Boolean function at a given
d-bit input. This is an inherent property of OV that is independent of the computational model.
2. Because we are working with simple computational models, we can generally make the following kind
of claim: given an algorithm for solving OV and given a partial assignment to all input vectors except
for one appropriately chosen vector, we can propagate this partial assignment through the algorithm,
and “shrink” the size of the algorithm by a factor of Ω(n). This sort of argument was first used by
Nechiporuk [Nec66] in the context of branching program lower bounds, and can be also applied to
formulas.
Combining the two ideas, if we can “shrink” our algorithm by a factor of n by restricting the inputs
appropriately, and argue that the remaining subfunction requires circuits of size Ω̃(min(2d , n)), we can
conclude that the original algorithm for OV must have had size Ω̃(min(n2d , n2 )). (Of course, there are
many details to verify, but this is the basic idea.)
The small AC0 formulas for OV(p) (the average-case setting) involve several ideas. First, given the
probability p ∈ (0, 1) of 1 and the number of vectors n, we observe a simple phase transition phenomenon:
there is only a particular range of dimensionality d in which the problem is non-trivial, and outside of this
range, almost all instances are either “yes” instances or “no” instances. Second, within this “hard” range
of d, the orthogonal vector pairs are expected to have a special property: with high probability, at least
one orthogonal pair in a “yes” instance has noticeably fewer ones than a typical vector in the distribution.
To obtain a sub-quadratic size AC0 formula from these observations, we partition the instance into small
groups such that the orthogonal pair (if it exists) is the only “sparse” vector in its group, whp. Over all pairs
of groups i, j in parallel, we take the component-wise OR of all sparse vectors in group i, and similarly for
group j. Then we test the two ORed vectors for orthgonality. By doing so, if our formula ever reports 1,
then there is some orthogonal pair in the instance (even in the worst case).

2 Lower Bounds
Functions that are hard on the middle layer of the hypercube. In our lower bound proofs, we will use
functions on d-inputs for which
every small circuit fails to agree with the function on inputs of Hamming

weight about d/2. Let [d]
denote
the set of all d-bit vectors of Hamming weight k.
k

Lemma 2.1. Let d be even, let C be a set of Boolean functions, let N (d, s) be the number of functions in C
d
on d inputs of size at most s, and let s⋆ ∈ N satisfy log2 (N (d, s⋆ )) < d/2
.


[d]
d
× {0, 1}, such that every function f : {0, 1}d →
pairs (xi , yi ) ∈ d/2
Then there is a sequence of d/2

d
{0, 1} satisfying f (xi ) = yi (for all i = 1, . . . , d/2
) requires C-size at least s⋆ .

d
Proof. By definition, there are N (d, s) functions of size s on d inputs from C, and there are 2(d/2) in[d] 
× {0, 1} defined over all d-bit vectors of Hamming weight d/2. For
put/output sequences (xi , yi ) d/2
d
2(d/2) > N (d, s), there is an input/output sequence that is not satisfied by any function in C of size s.

4

Note that it does not matter what is meant by size in the above lemma: it could be gates, wires, etc., and
the lemma still holds (as it is just counting). The above simple lemma applies to formulas, as follows:

[d] 
d
× {0, 1}, such that every
Corollary 2.1. Let c ≥ 2 be a constant. There are d/2
pairs (xi , yi ) ∈ d/2

d
function f : {0, 1}d → {0, 1} satisfying f (xi ) = yi (for all i = 1, . . . , d/2 ) needs c-fan-in formulas of
size at least Ω(2d /(d1/2 log d)).

Proof. There are N (d, s) ≤ dkc ·s formulas of size s on d inputs, where the constant kc depends only on c.
d

When 2(d/2) > dkc ·s , Lemma 2.1 says that there is an input/output sequence of length d that no formula
d/2

of size s can satisfy. Thusto satisfy thatsequence, we need a formula of size s at least large enough that
d
d 
2(d/2) ≤ dkc ·s , i.e., s ≥ Ω
/ log(d) ≥ Ω(2d /(d1/2 log d)).
d/2

2.1 Lower Bound for Constant Fan-in Formulas
We are now ready to prove the lower bound for Boolean formulas of constant fan-in:
Reminder of Theorem 1.1 For every constant c ≥ 1, OV on n vectors in d dimensions does not have
c-fan-in formulas of size O(min{n2 /(log d), n · 2d /(d1/2 log d)}), for all sufficiently large n, d.

All of the lower bound proofs have a similar structure. We will give considerably more detail in the proof
of Theorem 1.1 to aid the exposition of the later lower bounds.

Proof. To simplify the calculations, assume d is even in the following. Let Fn,d (v1 , . . . , vn ) be a c-fan-in
formula of minimal size s computing OV on n vectors of dimension d, where each vi denotes a sequence of
d Boolean variables (vi,1 , . . . , vi,d ).
Let ℓ be the number of leaves of Fn,d . Since Fn,d is minimal, each gate has fan-in at least two (gates of
fan-in 1 can be “merged” into adjacent gates). Therefore (by an easy induction on s) we have
s ≥ ℓ ≥ s/2.

(1)

Observe there must be a vector vi⋆ (for some i⋆ ∈ [n]) whose d Boolean variables appear on at most ℓ/n
leaves of the formula Fn,d .
[d] 
d 
Case 1. Suppose d/2
≤ n − 1. Let {(xi , yi )} ⊆ d/2
× {0, 1} be a set of hard pairs from Corollary 2.1,
[d] 
d
and let f : {0, 1} → {0, 1} be any function that satisfies f (xi ) = yi , for all i. Let {x′1 , . . . , x′t } ⊆ d/2
d 
be those d-bit strings of Hamming weight d/2 such that f (x′i ) = 1, for some t ≤ d/2
≤ n − 1. By

Corollary 2.1, such an f needs c-fan-in formulas of size at least Ω(2d /(d1/2 log d)).
d 
Case 2. Suppose d/2
≥ n − 1. Then we claim there is a list of input/output pairs (x1 , y1 ), . . .,
[d] 
(xn−1 , yn−1 ) ∈ d/2 × {0, 1} such that for every f : {0, 1}d → {0, 1} satisfying f (xi ) = yi , for all i, f
needs formulas of size at least Ω(n/ log d). To see this, simply note that if we take n − 1 distinct strings
d
x1 , . . . , xn−1 from d/2
, there are 2n−1 possible choices for the list of pairs. So when 2n−1 > dkc ·s , there
is a list (x1 , y1 ), . . ., (xn−1 , yn−1 ) that no formula of size s satisfies. For any function f : {0, 1}d →
{0, 1} such that f (xi ) = yi for all i = 1, . . . , n − 1, its formula size s ≥ Ω(n/ log d) in this case. Let
[d] 
be those d-bit strings of Hamming weight d/2 such that (x′i , 1) is on the list, for some
{x′1 , . . . , x′t } ⊆ d/2
t ≤ n − 1.
5

d 
For either of the two cases, we will use the list of t ≤ min{n − 1, d/2
} strings {x′1 , . . . , x′t } to make
assignments to the variables vi of our OV formula, for all i 6= i⋆ . In particular, for all i = 1, . . . , t with
i 6= i⋆ , we substitute the d bits of x′i (the complement of xi , obtained by flipping all the bits of x′i ) in place
of the d-bit input vector vi . If t < n − 1 (which can happen in case 1), substitute all other z~j with j 6= i⋆
with ~1. Note that all of the pairs of vectors substituted so far are not orthogonal to each other: for all i 6= i′ ,
6 0, because both x′i and x′i′ are distinct vectors each with d/2 ones, and for all i we have
we have hx′i , x′i′ i =
hx′i , ~1i =
6 0.

After these substitutions, the remaining formula Fn′ is on only d inputs, namely the vector vi⋆ . Moreover,
is a formula with at most ℓ/n leaves labeled by literals: the rest of the leaves are labeled with 0/1
constants. After simplifying the formula (replacing all gates with some 0/1 inputs by equivalent functions
of smaller fan-in, and replacing gates of fan-in 1 by wires), the total number of leaves of Fn′ is now at most
ℓ/n. Therefore by (1) we infer that
Fn′

size(Fn′ ) ≤ 2ℓ/n.

(2)

Since Fn,d computes OV, it follows that for every input vector y ∈ {0, 1}d of Hamming weight d/2, Fn′ on
input y outputs 1 if and only if there is some i such that hx′i , yi = 0. Note that since both x′i and y have
Hamming weight exactly d/2, we have hxi , yi = 0 if and only if y = xi .
By our choice of xi ’s, it follows that for all y ∈ {0, 1}d of Hamming weight d/2, Fn′ (y) = 1 if and only
if f (y) = 1. By our choice of f (from Corollary 2.1 in case 1, and our claim in case 2), we must have
size(Fn′ ) ≥ min{Ω(2d /(d1/2 log d)), Ω(n/ log d))},
depending on whether

d 
d/2

(3)

≤ n − 1 or not (case 1 or case 2). Combining (2) and (3), we infer that

ℓ ≥ Ω(n · min{Ω(2d /(d1/2 log d)), Ω(n/ log d))}),

(4)


n 2
o
n
n·2d
therefore the overall lower bound on formula size is s ≥ Ω min log
.
,
d d1/2 log d
Remark on a Red-Blue Variant of OV. In the literature, OV is sometimes posed in a different form,
where half of the vectors are colored red, half are colored blue, and we wish to find a red-blue pair which
is orthogonal. Calling this form OV’, we note that OV’ also exhibits the same lower bound up to constant
factors. Given an algorithm/formula/circuit A for computing OV’ on 2n vectors (n of which are red, and
n of which are blue), it is easy to verify that an algorithm/formula/circuit for OV on n vectors results by
simply putting two copies of the set of vectors in the red and blue parts. Thus our lower bounds hold for the
red-blue variant as well.

2.2 Lower Bound for Branching Programs
Recall that a branching program of size S on n variables is a directed acyclic graph G on S nodes, with
a distinguished start node s and exactly two sink nodes, labeled 0 and 1 respectively. All non-sink nodes
are labeled with a variable xi from {x1 , . . . , xn }, and have one outgoing edge labeled xi = 1 and another
outgoing edge labeled xi = 0. The branching program G evaluated at an input (a1 , . . . , an ) ∈ {0, 1}n is
the subgraph obtained by only including edges of the form xi = ai , for all i = 1, . . . , n. Note that after such

6

an evaluation, the remaining subgraph has a unique path from the start node s to a sink; the sink reached on
this unique path (be it 0 or 1) is defined to be the output of G on (a1 , . . . , an ).
Reminder of Theorem 1.2 OV on n vectors in d dimensions does not have branching programs of size
O(min{n2 , n · 2d /(d1/2 )}/(log(nd) log(d))), for all sufficiently large n, d.
Proof. (Sketch) The proof is similar to Theorem 1.1; here we focus on the steps of the proof that are
different. Let G be a branching program with S nodes computing OV on n vectors with d dimensions. Each
node of G reads a single input bit from one of the input vectors; thus there is an input vector vi⋆ that is read
only O(S/n) times in the entire branching program G.
We will assign all variables other than the d variables that are part ofvi⋆ . Using the same encoding as
Theorem 1.1, by assigning the n − 1 other vectors, we can implement a function f : {0, 1}d → {0, 1} that is
[d] 
. In particular, we substitute d-bit
hard for branching programs to compute on the set of d-bit inputs in d/2

[d]
vectors which represent inputs from f −1 (1) ∩ d/2 for all n − 1 input vectors different from vi⋆ . For each
of these assignments, we can reduce the size of the branching program accordingly: for each input bit xj
that is substituted with the bit aj , we remove all edges with the label xj = ¬aj , so that every node labeled
xj now has outdegree 1. After the substitution, two properties hold:
1. There is a hard function f such that the minimum size
T of a branching program computing f on
d 
the n − 1 inputs satisfies T log2 (T ) ≥ Ω(min{ d/2
, n}/ log(d)). To see this is possible, first note
there are dT · 2Θ(T log(T )) branching programs of size T on d inputs (there are dT choices for the
node labels, and 2Θ(T log(T )) choices for the remaining graph on T nodes). In contrast, there are at
d
min{(d/2
),n−1} choices for the hard function f ’s values on d-bit inputs of Hamming weight d/2.
least 2
d
min{(d/2
),n−1} , or
Therefore there is a function f such that dT · 2Θ(T log(T )) ≥ 2



d
T + Θ(T log(T )) ≥ min
, n − 1 / log2 (d).
d/2

2. The minimum size of a branching program computing a function f : {0, 1}d → {0, 1} on the remaining d bits of input is at most O(S/n). This follows because every node v with outdegree 1 can be
removed from the branching program without changing its functionality: for every arc (u, v) in the
graph, we can replace it with the arc (u, v ′ ), where (v, v ′ ) is the single edge out of v, removing the
node v.

n
o

d 
Combining these two points, we have (S/n) · log(S/n) ≥ Ω min d/2
, n / log(d) , or
S≥Ω

min{n

d
d/2

 2 !
,n }

log(S/n) · log(d)

.

Since S ≤ n2 d, we have
S≥Ω

min{n

d
d/2

 2 !
,n }

log(nd) · log(d)

≥Ω

This concludes the proof.
7

min{n · 2d /d1/2 , n2 }
log(nd) · log(d)

!

.

2.3 Formulas With Symmetric Gates
We will utilize a lower bound on the number of functions computable by symmetric-gate formulas with a
small number of wires:
Lemma 2.2. There are nO(w) symmetric-gate formulas with w wires and n inputs.
Proof. There is an injective mapping from the set of trees of unbounded fan-in and w wires into the set of
binary trees with at most 2w nodes: simply replace each node of fan-in k with a binary tree of at most 2k
nodes. The number of such binary trees is O(42w ) (by upper bounds on Catalan numbers). This counts the
number of “shapes” for the symmetric formula; we also need to count the possible gate assignments. There
are 2k+1 symmetric functions on k inputs. So for a symmetric-gate formula with g gates, where the ith gate
has fan-in wi for i P
= 1, . . . , g, the number of possible assignments of symmetric functions to its gates is
Q
g
wi +1 = 2g+ i wi = 2g+w . There are at most w leaves, and there are nw ways to choose the variables
2
i=1
read at each leaf. Since g ≤ w, we conclude that there are at most 42w · 22w · nw ≤ nO(w) symmetric-gate
formulas with w wires.
Reminder of Theorem 1.3 Every formula computing OV composed of arbitrary symmetric functions with
unbounded fan-in needs at least Ω(min{n2 /(log d), n · 2d /(d1/2 log d))}) wires, for all n and d.
Proof. (Sketch) The proof is quite similar to the other lower bounds, given Lemma 2.2, so we just sketch
the ideas. Let F be a symmetric-gate formula for computing OV with unbounded fan-in and w wires. Let
wi be the number of wires touching inputs and wg be the number of wires that do not touch inputs. Since F
is a formula, we have (by a simple induction argument) that wi ≥ wg , thus
w ≤ 2wi .

(5)

As before, each leaf of the formula is labeled by an input from one of the input n vectors; in this way, every
leaf is “owned” by one of the n input vectors. We will substitute a 0/1 variable assignment to all vectors,
except the vector z~⋆ which owns the fewest leaves. This gives a 0/1 assignment to all but O(wi /n) of the wi
wires that touch inputs.
After any such variable assignment, we can simplify F as follows: for every symmetric-function gate g
which has wg input wires with k wires assigned 0/1, we can replace g with a symmetric function g′ that has
only wg − k inputs, and no input wires assigned 0/1 (a partial assignment to a symmetric function just yields
another symmetric function on a smaller set of inputs). If g ′ is equivalent to a constant function itself, then
we remove it from the formula and substitute its output wire with that constant, repeating the process on the
gates that use the output of g as input. When this process completes, our new formula F ′ has d inputs and
no wires that are assigned constants. So F ′ has O(wi /n) wires touching inputs, and therefore by (5) the
total number of wires in F ′ is O(w/n).
d
min{n−1,(d/2
)} different functions on
As described earlier, the n − 1 vectors we assign can implement 2

d-bit inputs, but there are at most dO(w/n) functions computable by the symmetric formula remaining, by
d
min{n−1,(d/2
)} , or
Lemma 2.2. Thus we need that the number of wires w satisfies dO(w/n) ≥ 2
w ≥ Ω(min{n2 , n · 2d /(d1/2 )}/(log d)).
This completes the proof.
8

3 Small Formulas for OV in the Average Case
Recall that for p ∈ (0, 1) and for a fixed n and d, we say that OV(p)n,d is the distribution of OV instances
where all bits of the n vectors from {0, 1}d are chosen independently, set to 1 with probability p and 0 otherwise. We will often say that a vector is “sampled from OV(p)” if each of its bits are chosen independently
in this way. We would like to understand how efficiently OV(p)n,d can be solved on almost all instances
(i.e., with probability 1 − o(1)), for every n and d.

Reminder of Theorem 1.4 For every p ∈ (0, 1), and every n and d, there is an AC0 formula of size n2−εp
that correctly answers all but a on (1) fraction of OV(p)n,d instances on n vectors and d dimensions, for an
εp > 0 such that εp → 1 as p → 1.
Proof. Let ε > 0 be sufficiently small in the following. First, we observe that OV(p)n,d is very easy, unless
d is close to (2/ log2 (1/(1 − p2 ))) log 2 (n). In particular, for dimensionality d that is significantly smaller
(or larger, respectively) than this quantity, all but a o(1) fraction of the OV(p)n,d instances are “yes” (or
“no”, respectively). To see this, note that two randomly chosen d-dimensional vectors under the OV(p)n,d
distribution are orthogonal with probability (1 − p2 )d . For d = (2/ log 2 (1/(1 − p2 ))) log 2 (n), so a random
pair is orthogonal with probability
(1 − p2 )(2/ log2 (1/(1−p

2 ))) log

2 (n)

= 1/n2 .

Thus an OV(p)n,d instance with n vectors has nontrivial probability of being a yes instance for d approximately (2/ log 2 (1/(1 − p2 ))) log2 (n).

Therefore if d > (2/ log 2 (1/(1 − p2 )) + ε) log2 (n), or d < (2/ log 2 (1/(1 − p2 )) − ε) log2 (n), then
the random instance is either almost surely a “yes” instance, or almost surely a “no” instance, respectively.
These comparisons could be done with the quantities (2/ log2 (1/(1 − p2 )) − ε) log2 (n) and (2/ log 2 (1/(1 −
p2 ))+ε) log2 (n) (which can be hard-coded in the input) with a poly(d, log n)-size branching program, which
can output 0 and 1 respectively if this is the case.2
From here on, assume that d ∈ [(2/ log 2 (1/(1 − p2 )) − ε) log 2 (n), (2/ log 2 (1/(1 − p2 )) + ε) log2 (n)].
Note that for p sufficiently close to 1, the dimensionality d is δ log n for a small constant δ > 0 that is
approaching 0. Thus in the case of large p, the AC0 formula given in Proposition 1 has sub-quadratic size.
In particular, the size is
O(n · 2d · d) ≤ n1+2/ log2 (1/(1−p
For p ≥ 0.867 >

p

2 ))+o(1)

.

(6)

3/4, this bound is sub-quadratic. For smaller p, we will need a more complex argument.

Suppose u, v ∈ {0, 1}d are randomly chosen according to the distribution of OV(p) (we will drop the n, d
subscript, as we have fixed n and d at this point).

We now claim that, conditioned on the event that u, v is an orthogonal pair, both u and v are expected to
have between (p/(1 + p) − ε)d and (p/(1 + p) + ε)d ones, with 1 − o(1) probability. The event that both
u[i] = v[i] = 1 holds with probability 1 − p2 ; conditioned on this event never occurring, we have
Pr[u[i] = 0, v[i] = 0 | ¬(u[i] = v[i] = 1)] = (1 − p)2 /(1 − p2 ),

Pr[u[i] = 1, v[i] = 0 | ¬(u[i] = v[i] = 1)] = p(1 − p)/(1 − p2 ),

Pr[u[i] = 0, v[i] = 1 | ¬(u[i] = v[i] = 1)] = p(1 − p)/(1 − p2 ).

2

As usual, poly(m) refers to an unspecified polynomial of m of fixed degree.

9

Hence the expected number of ones in u (and in v) is only p(1 − p)d/(1 − p2 ) = pd/(1 + p), and the number
of ones is within (−εd, εd) of this quantity with probability 1 − o(1). (For example, in the case of p = 1/2,
the expected number of ones is d/3, while a typical vector has d/2 ones.)
Say that a vector u is light if it has at most (p/(1 + p) + ε)d ones. It follows from the above discussion
that if an OV(p) instance is a “yes” instance, then there is an orthogonal pair with two light vectors, with
probability 1 − o(1). Since the expected number of ones is pd, the probability that a randomly chosen u is
light is






p
ε
p
2
+ ε d = pd 1 −
+
Pr u has at most
ones ≤ e−(p/(p+1)+ε/p) pd/2
1+p
p+1 p
= e−(p

3 /(2(p+1)2 )−Θ

p (ε))d

,

by a standard Chernoff tail bound (see Theorem A.1 in Appendix A). So with high probability, there are at
3
2
most n · e−(p /(2(p+1) )−Θp (ε))d = n1−α light vectors in an OV(p) instance, where
α=

p3
+ Θp (ε) · 2/(log 2 (1/(1 − p2 ))).
(p + 1)2 log2 (1/(1 − p2 ))

Divide the n vectors of the input arbitrarily into n1−α(1−ε) groups G1 , . . . , Gn1−α(1−ε) , of O(nα(1−ε) )
vectors each. WLOG, suppose an orthogonal pair u, v lies in different groups u ∈ Gi and v ∈ Gj , with i 6= j
(note that, conditioned on there being an orthogonal pair, this event also occurs with 1 − o(1) probability).
Since every vector is independently chosen, and given that Prv [v is light ] ≤ 1/nα , note that
Pr

v1 ,...,vnα(1−ε)

[all vi in group Ga are not light] ≥ (1 − 1/nα )n

α(1−ε)

≥ 1 − 1/nεα ,

for every group Ga . Thus the groups Gi and Gj have at most one light vector with probability 1 − o(1).

We can now describe our formula for OV(p), in words. Let Light(v) be the function which outputs 1 if and
only if the d-bit input vector v is light. Since every symmetric function has poly(d)-size formulas [Khr72],
Light(v) also has poly(d)-size formulas. Here is the formula:
Take the OR over all n2−2α(1−ε) pairs (i, j) ∈ [n1−α(1−ε) ]2 with i < j:
Take the ¬OR over all k = 1, . . . , d, of the AND of two items:
1. The OR over all O(nα(1−ε) ) vectors u in group Gi of (Light(u) ∧ u[k]).
2. The OR over all O(nα(1−ε) ) vectors v in group Gj of (Light(v) ∧ v[k]).
To see that this works, we observe:
• If there is an orthogonal pair u, v in the instance, then recall that with probability 1 − o(1), (a) u and
v are light, (b) u and v appear in different groups Gi and Gj , and (c) there are no other light vectors
in Gi and no other light vectors in Gj . Thus the inner ORs over the group Gi (and respectively Gj )
will only output the bits of the vector u (and respectively v). Thus the above formula, by guessing
the pair (i, j), and checking over all k = 1, . . . , d that (u[k] ∧ v[k]) is not true, will find that u, v are
orthogonal, and output 1.

10

• If there is no orthogonal pair, then we claim that the formula always outputs 0. Suppose the formula
outputs 1. Then there is some (i, j) ∈ [n1−α(1−ε) ]2 such that the inner product of two vectors Vi and
Wj is 0, where Vi is the OR of all light vectors in group Gi and Wj is the OR of all light vectors
in group Gj . But for these two vectors to have zero inner product, it must be that all pairs of light
vectors (one from Gi and one from Gj ) are orthogonal to each other. Thus there is an orthogonal pair
in the instance.
Using the poly(d)-size formulas for Light, the DeMorgan formula has size
O(n2−2α(1−ε) · d · nα(1−ε) · poly(d)) ≤ O(n2−α(1−ε) · poly(d)).

(7)

Substituting in the value for α, the exponent becomes
2−

2
p3 (1 − ε)
+ Θp (ε) ·
.
2
2
(p + 1) log2 (1/(1 − p ))
log2 (1/(1 − p2 ))

Recalling that we are setting ε to be arbitrarily small (its value only affects the o(1) probability of error), the
formula size is
3
n

2−

p
+o(1)
2(p+1)2 log2 (1/(1−p2 ))

.

Observe that our formula can in fact be made into an AC0 formula of similar size; this is easy to see except
for the poly(d)-size formula for Light. But for d = O(log n), any formula of poly(log n)-size on O(log n)
ε
bits can be converted into an AC0 circuit of depth c/ε and size 2(log n) , for some constant c ≥ 1 and any
desired ε > 0.
The final formula is the minimum of the formulas of (6) and (7). For every fixed p ∈ (0, 1], we obtain a
bound of n2−εp for an εp > 0.

4 Conclusion
It is important to note that the largest known lower bound for branching programs computing any explicit
function is due to Neciporuk [Nec66] from 1966, and is only Ω(N 2 / log2 N ) for inputs of length N . A
similar statement holds for Boolean formulas over the full binary basis (see for example [Juk12]). Our
lower bounds for OV match these bounds up to polylogarithmic factors. Thus it would be a significant
breakthrough to generalize our results to other problems believed to require cubic time, such as:
3-O RTHOGONAL V ECTORS (3-OV)
Given: n vectors v1 , . . . , vn ∈ {0, P
1}d
Decide: Are there i, j, k such that dℓ=1 vi [ℓ] · vj [ℓ] · vk [ℓ] = 0?
It is known that the Strong Exponential Time Hypothesis also implies that 3-OV requires n3−o(1) for
dimensionality d = ω(log n) [Wil04, AV14].
Acknowledgements. We are very grateful to Ramamohan Paturi for raising the question of whether the
OV conjecture is true for AC0 circuits.
11

References
[ABH+ 16] Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and
Or Zamir. Subtree isomorphism revisited. In SODA, pages 1256–1271, 2016.
[ABV15]

Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for
LCS and other sequence similarity measures. In FOCS, pages 59–78, 2015.

[APRS16] Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, and Francesco Silvestri. On the
complexity of inner product similarity join. In PODS, pages 151–164, 2016.
[AV14]

Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower
bounds for dynamic problems. In FOCS, pages 434–443, 2014.

[AVW14]

Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster
alignment of sequences. In ICALP, pages 39–51, 2014.

[AVW16]

Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed
parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA, pages
377–391. Society for Industrial and Applied Mathematics, 2016.

[AWY15] Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More applications of the polynomial
method to algorithm design. In SODA, pages 218–230, 2015.
[BBK+ 16] Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer, and André Schulz. Finegrained analysis of problems on curves. In EuroCG, Lugano, Switzerland, 2016.
[BI15]

Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic
time (unless SETH is false). In STOC, pages 51–58, 2015.

[BI16]

Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match?
FOCS, pages 457–466, 2016.

[BK15]

Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In FOCS, pages 79–97, 2015.

[BM16]

Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. JoCG,
7(2):46–76, 2016.

[Bri14]

Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In FOCS, pages 661–670, 2014.

In

[BRSV17] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case finegrained hardness. IACR Cryptology ePrint Archive, 2017:202, 2017.
[CDHL16] Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, and Veronika Loitzenbauer.
Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction. In LICS, pages 197–206, 2016.
[CGR16]

Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal
distances in undirected graphs. In SODA, pages 363–376, 2016.
12

[CIP09]

Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability
of small depth circuits. In Parameterized and Exact Complexity (IWPEC), pages 75–85, 2009.

[CST17]

Pairwise comparison of bit vectors. https://cstheory.stackexchange.com/questions/37361/
January 20, 2017.

[CW16]

Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and more:
Quickly derandomizing Razborov-Smolensky. In SODA, pages 1246–1255, 2016.

[ED16]

Jacob Evald and Søren Dahlgaard. Tight hardness results for distance and centrality problems
in constant degree graphs. CoRR, abs/1609.08403, 2016.

[GIKW17] Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness
for first-order properties on sparse structures with algorithmic applications. In SODA, pages
2162–2181, 2017.
[IP01]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst.
Sci., 62(2):367–375, 2001.

[IR16]

Costas S. Iliopoulos and Jakub Radoszewski. Truly subquadratic-time extension queries and
periodicity detection in strings with uncertainties. In 27th Annual Symposium on Combinatorial
Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel, pages 8:1–8:12, 2016.

[Juk12]

Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012.

[Khr72]

V. M. Khrapchenko. The complexity of the realization of symmetrical functions by formulae.
Mathematical notes of the Academy of Sciences of the USSR, 11(1):70–76, 1972.

[KPS17]

Marvin Künnemanm, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity
of one-dimensional dynamic programming. CoRR, abs/1703.00941, 2017.

[Nec66]

E. I. Nechiporuk. On a boolean function. Doklady of the Academy of Sciences of the USSR,
169(4):765–766, 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999–
1000.

[Pri99]

Paul Pritchard. A fast bit-parallel algorithm for computing the subset partial order. Algorithmica, 24(1):76–86, 1999.

[RV13]

Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013.

[Weh16]

Michael Wehar. Intersection non-emptiness for tree-shaped finite automata. Available at
http://michaelwehar.com/documents/TreeShaped.pdf, February 2016.

[Wil16]

Richard Ryan Williams. Strong ETH breaks with merlin and arthur: Short non-interactive
proofs of batch evaluation. In 31st Conference on Computational Complexity, CCC 2016, May
29 to June 1, 2016, Tokyo, Japan, pages 2:1–2:17, 2016.

[Wil04]

Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications.
Theor. Comput. Sci., 348(2-3):357–365, 2005. See also ICALP’04.

[WY14]

Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA,
pages 1867–1877, 2014.
13

A

Chernoff Bound

We use the following standard tail bound:
Theorem A.1. Let p ∈ (0, 1) and let X1 , . . . , Xd ∈ {0, 1} be independent random variables, such that for
all i we have Pr[Xi = 1] = p. Then for all δ ∈ (0, 1),
"
#
X
2
Pr
Xi > (1 − δ)pd ≤ e−δ pd/2 .
i

B DeMorgan Formulas into Branching Programs
Here we describe at a high level how to convert a DeMorgan formula (over AND, OR, NOT) of size s into
a branching program of size O(s).
Our branching program will perform an in-order traversal of the DeMorgan formula, maintaining a counter
(from 1 to s) of the current node being visited in the formula. The branching program begins at the root
(output) of the formula. If the current node is a leaf, its value b is returned to the parent node. If the current
node is not a leaf, the branching program recursively evaluates its left child (storing no memory about the
current node).
The left child returns a value b. If the current node is an AND and b = 0, or the current node is an OR and
b = 1, the branching program propagates the bit b up the tree (moving up to the parent). If the current node
is a NOT then the branching program moves to the parent with the value ¬b.
If none of these cases hold, then the branching program erases the value b, and recursively evaluates the
right child, which returns a value b. This value is simply propagated up the tree (note the fact that we visited
the right child means that we know what the left child’s value was).
Observe that we only hold the current node of the formula in memory, as well as O(1) extra bits.

14

