On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance

Problem

Jakob Pagter^{∗}

BRICS^{†} Department of Computer Science University of Aarhus Denmark

Abstract

Miklos Ajtai [Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions, 31st Symposium on Theory of Computation (STOC), 1999] has proved that any R-way branching program deciding the so-called Hamming distance problem (given n elements decide whether any two of them have “small” Hamming distance): in time O(n) must use space Ω(n lg n).

We extend the proof to obtain a time-space trade-off for time between n and αn \frac{lg n}{lg lg n}, for some suitable 0 < α < 1. In particular we prove that if space is O(n^{1−ϵ}), then time is Ω(n \frac{lg n}{lg lg n}).

1 Introduction

In [Ajt99b] Miklos Ajtai proved that any R-way branching program that decides element distinctness using sub-linear space must use super-linear time. The technical details of the proof are complicated. However, the basic ideas underlying the proof are not, and this was exploited by Ajtai to prove an even stronger bound for the so called Hamming distance problem (a generalization of element distinctness) using much simpler arguments. An interesting aspect of these bounds is that they are valid in the well known RAM model with word size lg R, and thus bounds in this model are valid for RAMs independent on the specific instruction set.

∗E-mail: pagter@daimi.au.dk. Partially supported by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT). Part of this work was done while the author was visiting University of Toronto.

†

Basic Research in Computer Science,

Centre of the Danish National Research Foundation.

The element distinctness theorem is the more interesting of Ajtai’s two theorems, as element distinctness is an interesting and very well-studied problem [BFMadH^{+}87, Kar86, Yao94]. On the other hand, the Hamming distance proof is arguably the more interesting of the two proofs, as it is gives the best possible bound in the model using a clear and elegant proof.

The purpose of this paper is to study the latter proof from three angles:

1) To what extent does the Hamming distance proof generalize, i.e. for what intervals of time and space do we have a lower bound in the form of a timespace trade-off? 2) How strong is the proof, e.g. can the simpler of the two proofs actually be used to prove something for element distinctness? 3) Can the Hamming distance proof be used to give non-trivial lower bounds in the Boolean model?

The answer to the two latter questions seems to be negative, but we can generalize the proof to achieve the following:

Theorem 1 (General theorem, vanilla version) Any R-way branching program deciding Hamming distance using time O(k(n)·n) , k(n) < α\frac{lg n}{lg lg n}^{1} for a suitable constant 0 < α < 1 must use space

S(n) > β \frac{n lg n}{k(n)^{10k(n)}} ,

for some constant β > 0.

The full version of this theorem (to be found in Section 5) will imply all three answers. For now, let us just observe that Theorem 1 implies that any R-way branching program, and thus any RAM with word size lg R, solving the Hamming Distance problem using O(n^{1−ϵ}) bits of space must use time Ω(n\frac{lg n}{lg lg n}). In terms of time this is the strongest result that can be achieved using our results. To our knowledge this is the quantitatively best known lower bound for a decision problem in the R-way branching program model. Similarly, using time O(n\frac{lg n}{lg lg n})) implies using space Ω(n^{1−ϵ}) for some 0 < ϵ < 1.

Using the combinatorics of Ajtai in conjunction with the technique of Beame et al. [BST98], a theorem similar to Ajtai’s Hamming distance theorem can be proved. In fact this gives rise to a Ω(n lg lg n) bound on time for space in O(n^{1−ϵ}). This connection was observed by Beame et al. [BSSV00] (independently on this work). It is not surprising then that we can also prove Theorem 1 by combining the techniques of Beame et al. [BSSV00] with our generalized version of Ajtai’s combinatorics (see [Pag01]). Since the initial version of our paper (available as [Pag00]), Beame et al. [BSSV03] has provided an Ω(n lg n) bound on time for space in O(n^{1−ϵ}) for the Hamming distance problem.

Our main contribution is the generalization of Ajtai’s technical lemmata. Using the generalized version of Ajtai’s combinatorics we are able to prove lower bounds for time up to Ω(n\frac{lg n}{lg lg n}), improving the Ω(n lg lg n) bound of Beame et al., and the Ω(n\frac{lg lg n}{lg lg lg n}) bound, which follows by the immediate generalization of Ajtai’s work (where constants are systematically replaced by functions of n without modifying the proof as such). We observe that the proof also works for randomized branching programs with one-sided error.

1Following [Knu98] we use “lg” to denote the logarithm in base 2.

2 Previous work

Proving lower bounds in general models of computation is notoriously hard. Early approaches restricted the computational model, for example to comparison based models, but natural models (such as the RAM) do not obey such restrictions. Another approach has been to restrict the resources available, e.g. limiting the amount of space which we allow a given algorithm to use. This gives rise to time-space trade-offs, for which several breakthroughs have been achieved recently [Ajt99a, Ajt99b, BST98].

Branching programs have been very useful for this line of study. In particular much insight has been gained using the R-way branching program model of Borodin and Cook [BC82]. Results include general lower bounds for sorting [Bea91, BC82] and universal hashing [MNT93]. The problems for which these techniques work are characterized by having a large output domain, which is essential for the employed proofs. It was only recently that non-trivial lower bounds for a decision problem were obtained in this model [Ajt99b, BST98].

When proving upper bounds for problems like Hamming distance, element distinctness, sorting and universal hashing, one popular model has been the word RAM, or RAM, (see e.g. [Hag98]). Much debate has taken place over which instruction sets to allow, giving rise to some confusion in the literature. However, one of the very nice properties of R-way branching programs is that they are strictly more powerful than any RAM with word size lg R (regardless of instruction set). This means that the bounds obtained in this model will hold for any RAM no matter what specific instruction set we are working with.

The first non-trivial bound for a decision problem in the R-way branching program model was given by Beame et al. [BST98], who exhibited a problem for which they could prove a lower bound of Ω(n lg lg n) bound on time, when restricting space to being O(n). As mentioned earlier, this bound also applies to the Hamming distance problem.

Independently of our work Beame et al. [BSSV00] generalized the element distinctness proof of Ajtai, and obtained a lower bound of Ω(n\sqrt{lg n/ lg lg n}) for Element Distinctness in the R-way model. Our results differ from this result in two aspects: 1) we focus on the “easy” version of Ajtai’s original proof—the Hamming distance proof, and 2) quantitatively our bounds are better (albeit for Hamming distance and not element distinctness). Since the initial version of our paper Beame et al. [BSSV03] (a revision of [BSSV00]) has provided an Ω(n lg n) bound on time for space in O(n^{1−(ϵ}) for the Hamming distance problem, improving on our bounds.

Many of the results achieved in the R-way branching program model were stepping stones or “side-effects” in the quest for a non-trivial (i.e. T ∈ ω(n) or even just T > n) for a decision problem in a Boolean model, which for a great many people is the holy grail of computational complexity. The first non-trivial bound for a decision problem in the Boolean branching program model was given by Beame et al. [BST98], who exhibited a problem for which they could prove a lower bound of 1.0178 n (sic) on time for space restricted to being sublinear. Ajtai [Ajt99a] extended his own work for element distinctness in the Rway model to give a non-trivial lower bound in the Boolean branching program model. The aforementioned work of Beame et al. [BSSV00] generalizes [Ajt99a] (as well as [Ajt99b]) to obtain lower bounds for time up to Ω(n\sqrt{lg n/ lg lg n}) in the Boolean branching program model.

Despite the exciting developments in the Boolean model, our focus remains the R-way model. We only treat the Boolean model via the fact that bounds in the Boolean branching program model can be derived from bounds obtained in the R-way model—at a cost.

Proposition 1 Suppose we can prove a lower bound of f(n) for some problem in the R-way branching program model, then this translates into a f(n)/ lg R lower for the same problem in the Boolean branching program model. Likewise for space.

Proof: In the Boolean model we measure the size of the input, n, in bits. In the R-way model n refers to the number of words each consisting of lg R bits. Thus, if we translate inputs of size n from the R-way model, they will become inputs of size n lg R bits in the Boolean model. □

So if we have that R ∈ n^{O(1)}, we need ω(n lg n) bounds in the R-way model to infer ω(n) bounds in the Boolean model. None of the results mentioned for decision problems in the R-way branching program model—our results included— meet this requirement.

The results of Beame et al. [BSSV00, BSSV03] holds for randomized branching programs with two-sided error. These are the first non-trivial lower bounds for randomized branching programs in both the R-way and the Boolean branching program model.

3 Model of computation

We employ the R-way branching program model, which is at least as strong as a RAM with word size ⌈lg R⌉ and any instruction set. We will only give an informal presentation of the model. For a detailed account see [BC82] or [Sav98]. Boolean branching programs are the special case of R = 2, corresponding to looking at one bit at a time.

An R-way branching program is a directed acyclic graph. It has one node with in degree 0 which is called the start node. Every node with out degree 0 is called a terminal node, and is labelled either “YES” or “NO”, depending on whether the branching program accepts or rejects the given input. Every node which is not a terminal node is called a computation node and is labelled with some index i (referring to the i’th word of the input). A computation node has exactly R outgoing edges, each with a unique label from 1, …, R. The input to the branching program consists of n elements from some universe of size R (which may be a function of n), and computation proceeds as follows: given input x ∈ {1, …, R}^{n}, we start in the start node where we read the word indexed by the label of this node; if the value in this word is r, then we follow the outgoing edge with label r. We continue this procedure for the computation nodes we encounter until we end up in some terminal node which tells us the result of the computation.

As measures of complexity we define time T to be the height of our branching program, and space S to be ⌈lg #nodes⌉.

For the rest of this paper we will assume all branching programs to be levelled, which means that we can partition the nodes into T disjoint sets V_{1}, V_{2}, … V_{T}, such that all edges originating from V_{i} go to V_{i+1}. For asymptotic purposes we may assume this without loss of generality. For proofs and definition see e.g. Borodin et al. [BFK^{+}81].

In this model of computation all “internal” computation is free, we only “pay” for reading the input.

4 The n-ary independence problem for a binary relation

We now describe a particular class of decision problems that are the focus of this paper. This class was introduced by Ajtai. Let Δ ⊆ U × U be a binary relation on universe U. Say that an input x = ⟨x(1), x(2), …, x(n)⟩ is Δ-independent if there is no i ≠ j such that Δ(x(i), x(j)). The n-ary independence problem for Δ is the decision problem D_{Δ} on U^{n} defined by D_{Δ}(x) = “YES” if and only if x is Δ-independent.

For example, in the case that Δ is the equality relation EQ = {(x, x)|x ∈ U}, the n-ary independence problem for EQ is equivalent to element distinctness on U^{n}.

As a consequence of the fact mentioned above that all internal computation is free, we have the following easy proposition.

Proposition 2 We can decide the n-ary independence problem, D_{Δ}, for any binary relation, Δ, on U in time T and space S such that

T ·S ∈ O(n^{2} lg R),

for time between n and n^{2}.

Proof: First observe that in time n we may decide Δ using R^{n} nodes or n lg R bits of space, using an R-way decision tree—i.e. reading all the inputs once, remembering them, and then exploit the free internal computation.

This easily generalizes by splitting the input into b(n) blocks each containing n/b(n) words. Now what we will do is do decide Δ for each of the O(b(n)^{2}) pairs of blocks; each time we read a block we also decide Δ for every pair of elements in that block. For each pair we may do the computation in time 2n/b(n) using 2(n/b(n)) lg R bits of space; deciding Δ internally on the blocks is free as we remember the entire block. In total we use time O(nb(n)) and space O((n/b(n)) lg R), yielding the desired trade-off. □

For time n this construction of course works for any problem, which shows that for time Θ(n) one cannot give space-bounds better than Ω(n lg n) (when R = 2^{c lg n}), i.e. we cannot hope for a better general bound for any such independence problem in this model.

In this paper we focus on the case that U = {0, 1}^{c lg n} (where c will be a suitable fixed natural number) with |U| = n^{c}. Recall that our n-ary independence problems for binary relations are defined on x = ⟨x(1), x(2), …, x(n)⟩ ∈ U^{n}; we emphasize the difference in notation between x_{i} ∈ U^{n} (an entire input consisting of n elements from U) and x(i) ∈ U (the i’th element from U of the input x).

We will be concerned with the independence problem for another relation: the Hamming distance relation. For 0 < γ < \frac{1}{2} we define the parameterized Hamming distance relation HD_{γ}(a, b) ⊂ {0, 1}^{c lg n}×{0, 1}^{c lg n} which relates a and b if and only if they differ in at most γc lg n positions. To alleviate notation HD will refer to HD_{1/4} and Hamming distance, or D_{HD}, will refer to the n-ary independence problem for this relation with γ = 1/4. equality is the problem of deciding whether the input contains to identical words. It should be clear that Hamming distance is a natural generalization of equality ^{2}.

A relation Δ is said to be λ(n)−full iff for any pair of subsets of U of size bigger than λ(n)|U| there exists a pair of elements, one from each of the two subsets, satisfying the relation. Formally, Δ is λ(n)−full if the following holds

∀A, B ⊆ U : |A|, |B| > λ(n)|U| ⇒ ∃a ∈ A, b ∈ B : Δ(a, b)  (1)

It should be clear that equality is \frac{1}{2} − full, as any two subsets of U containing more than half of U will have a non-empty intersection. In [Ajt99b] it is proved that for all 0 < γ < \frac{1}{2}, HD_{γ}, and in particular HD, is 2^{−δ lg n} − full on U = {0, 1}^{c lg n} where c and δ are natural numbers suitably chosen (independent on n, but depending on γ) such that c > δ. This means that if we have two subsets of U of size bigger than 2^{(c−δ) lg n}, we are guaranteed to have two elements with low Hamming distance.

A relation Δ is said to be ζ(n)−sparse iff the number of inputs of length n for which the n-ary independence problem D_{Δ}(x) = “YES” is less than ζ(n)|U|^{n} (a ζ(n) fraction of all possible inputs). Intuitively this means that the n-ary independence problem for the binary relation, Δ, has many “NO” instances. In [Ajt99b] it is proved that for all 0 < γ < \frac{1}{2} HD_{γ} is \frac{1}{2} − sparse for a fixed c ∈ N (recall that |U| = n^{c}) and n sufficiently large. This means that for at least half of all input to Hamming distance the answer is “NO”. Ajtai [Ajt99b] also proves that equality is c_{=} − sparse for a suitable fixed c_{=} > 0.

2When Ajtai says element distinctness in [Ajt99b], he actually means the dual problem equality.

5 The result

We are now ready to state the result.

Theorem 2 (General theorem, full version) Let Δ be a λ(n)−full and (nontrivial) ζ(n)−sparse relation on U×U with |U| = R. Consider an R-way branching program deciding D_{Δ}, in time T (n) = k(n)·n and space S(n). If,

72 k(n) lg k(n) < lg \frac{1}{λ(n)},  (2)

and

lg \frac{1}{ζ(n)} < \frac{n lg \frac{1}{λ(n)}}{k(n)^{5k(n)}} .  (3)

Then,

S(n) ≥ \frac{n lg \frac{1}{λ(n)}}{k(n)^{4k(n)}} .  (4)

Let us discuss this theorem. First of all, many of the constants in the above statement may possibly be improved, albeit not significantly.

What kind of fullness is required to achieve a non-trivial result? ¿From Ajtai’s paper it might seem as if the Hamming distance proof works only for what we might call polynomial fullness, i.e., 1/|U|^{O(1)}-fullness, whereas the element distinctness (or rather equality) proof handles constant fullness. If k(n) ∈ O(1), we see from (2) that constant fullness, specifically λ(n) < 2^{−144}, actually does give rise to a non-trivial lower bound. However, it does not seem to be the case that the parameters of the proof can be improved enough to achieve anything for \frac{1}{2} − fullness, i.e., we cannot prove anything for element distinctness, but we can get closer than what Ajtai’s original statement suggests.

If λ(n)|U| < 1 the relation in question would be trivial to decide (as two subsets of size 1 would then be enough to ensure satisfaction of the fullness property), hence we can assume that λ(n)|U| ≥ 1. Combining this with (2) yields,

lg |U| ≥ lg \frac{1}{λ(n)} > 72 k(n) lg k(n).

Recalling Proposition 1, we see that the best result we can achieve in the Boolean model is,

\frac{T (n)}{lg |U|} < \frac{k(n)·n}{126 k(n) lg k(n)} ∈ o(n).

In conclusion, no matter how we might chose the parameters, we can get no non-trivial implications for the Boolean model.

As stated previously, on U = {0, 1}^{c lg n} Hamming distance is n^{δ} − full and \frac{1}{2} − sparse, giving Theorem 1 as corollary to Theorem 2. Interesting special cases include Ajtai’s original theorem: time in O(n) implies space in Ω(n lg n), and space O(n^{1−ϵ}) implies time Ω(n\frac{lg n}{lg lg n}).

6 Proof of Theorem 2

We would like to stress that almost all the arguments closely follow those of Ajtai [Ajt99b]. We give the proof in full detail for two reasons: 1) in the generalized version many constants, say c, are replaced by functions, c(n), and it is imperative to give the full proof to see exactly where the proof holds and where it breaks down; 2) it makes it clear exactly where we deviate from the original proof.

The proof presented here deviates from that of Ajtai in two aspects. When counting we use tighter estimates where it is possible, this has little effect on Ajtai’s original proof, but significantly extends the interval of time for which the generalized proof works—an immediate generalization will work for time up to roughly n\frac{lg lg n}{lg lg lg n}, whereas our proof works up to Θ(n\frac{lg n}{lg lg n}). Another deviation is our proof of Lemma 1 (corresponding to Lemmas 7 and 8 in [Ajt99b]). Besides these technical differences, changes have also been made for reasons of presentation.

The overall intuition behind Ajtai’s proof is as follows. We use the time and space restrictions to construct a large set of inputs that are all rejected by the algorithm. The structure and size of this set will be such that we can utilize the fullness property of our problem to ensure that at least one input, which we will call x_{fail}, in the above set must be accepted. This of course gives a contradiction on the assumed time and space restrictions of the algorithm.

Assume we have an R-way branching program, A, deciding D_{Δ} in time k(n)·n and space S(n) satisfying (2) and (3) but not (4). We will show that then there exists an input x such that A(x) = “NO” but D_{Δ}(x) = “YES”, contradicting our assumption that is, assuming (2) and (3) we may conclude (4).

Define state(x, t) as the state of A (one of 2^{S(n)}) after time step t on input x. For a time interval I, define state(x, I) to be state(x, t_{I}), where t_{I} is the last element of I that is, given x and a time interval I we get the state of the program when leaving I. An arbitrary set of times T may be written as a disjoint union of maximal intervals I_{j}, i.e. T = ∪_{j}I_{j}. If we assert that state(x, T) = state(y, T) we mean that ∀j : state(x, I_{j}) = state(y, I_{j}).

We will construct x_{fail} from another input x with some desirable properties. The first property is that D_{Δ}(x) = “NO” and hence A(x) = “NO”, as A is assumed to decide D_{Δ} correctly. Suppose that we have two disjoint subsets of indices W_{1}, W_{2} ⊂ {1, …, n} and two disjoint subsets of times T_{1}, T_{2} ⊂ {1, …, k(n)·n}. Suppose now that on input x the indices of W_{i} (i = 1, 2) are not read outside T_{i}; let

S_{i}^{x} ⊆ {x_{i}|( obtained by modifying x on W_{i} only)
∧ state(x, T_{i}) = state(x_{i}, T_{i})},

i.e. x and x_{i} are identical outside W_{i} and each time we leave T_{i} on both x and x_{i} we are in the same state. Hence A(x) = A(x_{i}) for all x_{i} ∈ S_{i}^{x} as the only differences between the two inputs are in W_{i} and hence “forgotten” when we leave T_{i}, the only place where W_{i} is read.

Based on x we can thus construct x_{1} and x_{2} such that A(x) = A(x_{1}) = A(x_{2}) = “NO”. As W_{1} and W_{2} are disjoint we may make these two different changes to x simultaneously, obtaining the input x_{fail}. We would like to ensure that A(x) = A(x_{fail}) = “NO”, but currently this might not be the case. The reason is that in the set of time intervals, say T_{1}, A is in principle able to look outside W_{1} and hence A might look at W_{2}. This is not a problem as long as x on W_{2} is unchanged, but when making the two changes simultaneously we no longer have any guarantee that the states are fixed. The way to eliminate this problem is to enforce that the indices of W_{j} are not read in T_{i} on x_{i}, removing the possibility that A detects the change in W_{2} when in T_{1} and vice versa.

We can now construct x_{fail} such that A(x_{fail}) = A(x) = “NO” by making changes to x on W_{1} and W_{2}. The plan is of course to choose x_{fail} such that D_{Δ}(x_{fail}) = “YES”, giving the desired contradiction. One way to achieve this is to have so many choices for each of x_{1} and x_{2} that we can put the fullness property into play. If S ⊂ U^{n}, let S(l) be S projected onto the l’th dimension (or index).

Proposition 3 Let W ⊆ {1, …, n} and let S ⊂ U^{n} be a set of inputs that are all identical outside W. If |S| > (λ(n)|U|)^{|W |} then for at least one l ∈ W it will be the case that |S(l)| > λ(n)|U|, i.e. some x(l) (over x’s in S) must take on more than λ(n)|U| values from U.

Proof: Suppose that ∀l ∈ W it is the case that |S(l)| ≤ λ(n)|U| then clearly |S| ≤ (λ(n)|U|)^{|W |}. □

If we have many different inputs on W_{i} to choose from, there will be an index for which we have many values to choose from, allowing us to exploit the fullness property.

Based on the above idea, we define a μ(n)−hard set, H_{A}, for a branching program A deciding D_{Δ} in time k(n)·n.

Definition 4 (Hard Set) A set of inputs H_{A} ⊂ U^{n} is called a μ(n)−hard set for a branching program A deciding D_{Δ} in time k(n)·n and space S(n) if we have

• W_{1}, W_{2} ⊂ {1, …, n} with W_{1} ∩ W_{2} = ∅ and |W_{i}| ≥ μ(n)·n,

• T_{1}, T_{2} ⊂ {1, …, k(n)·n} with T_{1} ∩ T_{2} = ∅, such that ∀x ∈ H_{A} :

• D_{Δ}(x) = “NO”.

• The indices of W_{i} are only read in T_{i} (on x).

• state(x, I_{ij}) is fixed for all the intervals comprising T_{i}—i.e. every time we

leave T_{i}, A will behave identically for all x ∈ H_{A}.

□

Further, if H is a hard set then for x ∈ H_{A} we define an input y to be H_{A}- similar to x if there exists inputs x_{1}, x_{2} ∈ H_{A} such that x and x_{1} differ only on indices in W_{1} and x and x_{2} differ only on indices in W_{2}, and y is obtained from x by changing the position indexed by W_{1} to match x_{1} and those indexed by W_{2} to match x_{2}. We then have the following:

Proposition 5 Let H_{A} be a hard set for a branching program A deciding D_{Δ}. For x ∈ H_{A}, if y is H_{A}-similar to x then A(x) = A(y) = “NO”.

Proof: Assume now that A is able to distinguish x and y. This means that these two inputs lead to different final states for the branching program. As x and y are identical outside the indices of W_{1} and W_{2}, then there must exist i and j such that state(x, I_{ij}) ≠ state(y, I_{ij}), i.e., some interval I_{j} ⊆ T_{i}.

Assume, without loss of generality, that i = 1. So, for some I_{1j} ⊆ T_{1} state(x, I_{1j}) ≠ state(y, I_{1j}). Let I_{1j} be the first such interval during the computation of A, hence x and y follow the same computation path until I_{1j}. By construction, also x_{1} and x_{2} follow this same path as x. Inside I_{1j} we only read indices in W_{1} and end up in a different state than state(x, I_{1j}) following a different path from x. However, we follow the exact same path as on x_{1} as y is identical to x_{1} on W_{1}, so we have that state(x, I_{1j}) ≠ state(x_{1}, I_{1j}) contradicting that x and x_{1} are in the same hard set. □

The proof of Theorem 2 splits naturally in three parts. In Lemma 1 we show that if we have a large hard set, we may obtain x_{1} and x_{2} in “many” ways (relative to the fullness property). Then in Lemma 2 we show that given the time and space restrictions there exists a “large” hard set (relative to the sparseness property). Finally these two lemmata are combined.

Lemma 1 Let Δ be a λ(n) − full relation on U, A be a branching program deciding D_{Δ} in time k(n)·n and space S(n), and let H_{A} be a μ(n)−hard set for A so that,

|H_{A}| > 4λ(n)^{μ(n)·n}|U|^{n},

then there exists some x ∈ H_{A} for which there exist x_{fail} which is H_{A}-similar to x, i.e. with A(x_{fail}) = “NO”, but with D_{Δ}(x_{fail}) = “YES”.

Proof: Define x_{|W}, where W ⊆ {1, …, n}, to be x where all values at positions in W are overwritten with some standard symbol, say ⊥ ∉ U. Suppose we have some set of inputs H_{A} ⊆ U^{n} and some set of indices W ⊆ {1, …, n}; define

S^{x} = {y ∈ H_{A}|x_{|W} = y_{|W} },  (5)

i.e. the set of elements in H_{A} which are identical to x outside W. We claim the following

#x ∈ H_{A} with |S^{x}| ≤ \frac{1}{4} \frac{|H_{A}|}{|U|^{n−|W |}} is less than \frac{1}{4}|H_{A}|.  (6)

Given W, define a partition of H_{A} according to S^{x}, i.e. x and y are in the same class if and only if S^{x} = S^{y} (thus y ∈ S^{x}, and x ∈ S^{y}). Clearly there are no more than |U|^{n−|W |} classes, as we have at most this many ways of choosing a y which is different from x outside W. The number of inputs in classes of size at most \frac{1}{4}|H_{A}|/(|U|^{n−|W |}) is at most this number (the maximum size of these classes) times |U|^{n−|W |} (the maximum total number of classes), implying (6).

Based on a hard set H_{A}, let S_{i}^{x} be defined as in (5) based on H_{A} and W_{i}. Clearly (6) holds for S_{1}^{x} and S_{2}^{x}, so these sets are relatively large for most inputs in H_{A}. We would like an x for which both S_{1}^{x} and S_{2}^{x} are large, but in principle the x’s that give large S_{1}^{x} might not be the same as those that give large S_{2}^{x} (and vice versa). According to (6), |S_{i}^{x}| ≥ \frac{1}{4}|H_{A}|/(|U|^{n−|W |}) for \frac{3}{4} of the elements in H_{A}, hence for \frac{1}{4} of these elements both S_{1}^{x} and S_{2}^{x} are no smaller than \frac{1}{4}|H_{A}|/(|U|^{n−|W |}); certainly for any H_{A}, W_{1} and W_{2}, this gives us an input x′ such that both S_{1}^{x′} and S_{2}^{x′} have this size.

Consider this particular input x′. Each pair of x_{1} ∈ S_{1}^{x′} and x_{2} ∈ S_{2}^{x′} gives rise to a different y H_{A}-similar to x′. Since |W_{i}| ≥ μ(n)·n we have that \frac{1}{4}|H_{A}|/(|U|^{n−|W |}) > (λ(n)|U|)^{|W_{i}|}, yielding that |S_{i}^{x′}| > (λ(n)|U|)^{|W_{i}|}. Hence, by Proposition 3 there must exists a pair of indices k_{1} ∈ W_{1} and k_{2} ∈ W_{2} taking on more than λ(n)|U| different values for all the inputs in S_{1}^{x′} and S_{2}^{x′} respectively. By the fullness property this implies that there exists x′_{1} ∈ S_{1}^{x′} and x′_{2} ∈ S_{2}^{x′} so that Δ(x′_{1}(k_{1}), x′_{2}(k_{2})). Define x_{fail} to be the input H_{A}-similar to x′ obtained from x′ by modifying x′ on W_{1} and W_{2} using x′_{1} and x′_{2} respectively. Thus D_{Δ}(x_{fail}) = “YES”. By Proposition 5 A(x_{fail}) = “NO” as x_{fail} is H_{A}- similar to x′. □

Lemma 2 Let Δ be a ζ(n)−sparse relation on U, A be a branching program deciding D_{Δ} in time k(n)·n and space S(n), and let μ(n) = k(n)^{−4k(n)}. A has a μ(n)−hard set of size

|H_{A}| ≥ \frac{ζ(n)|U|^{n}}{\binom{n}{μ(n)·n}^{2} (3k(n))^{8k(n)} 2^{4k(n)S(n)}} .

Proof: We start by constructing a partitioning P_{x} of the indices as follows. Split time into 9k^{2}(n) intervals of length^{3} n/(9k(n)). Two indices i and j are in the same class of P_{x} if and only if they are read in exactly the same intervals on input x. P′_{x} is P_{x} restricted to classes of P_{x} whose members are queried in at most 2k(n) time intervals on x. Finally Γ_{x} is P′_{x} restricted to classes whose size is at least n/(4|P′_{x}|).

For w ∈ Γ_{x}, define intervals(x, W) to be the intervals in which W is queried on input x. By construction, intervals(x, W) contains at most 2k(n) intervals for all W ∈ Γ_{x}.

Our restricted partitioning Γ_{x} has the following properties,

∀W ∈ Γ_{x} : |W | ≥ μ(n) · n,  (7)

3The interval length is parameterized in [Ajt99b], however the present choice leaves little room for improvement.

∀x : ∃W_{1}, W_{2} ∈ Γ_{x} : intervals(x, W_{1}) ∩ intervals(x, W_{2}) = ∅. (8)

It is a fact that no more than n/2 elements can be queried in more than 2k(n) intervals, since the branching program has length at most k(n)·n; hence P′_{x} covers at least n/2 elements. Classes of P′_{x} with size no greater than n/(4|P′_{x}|) can cover at most n/4 indices (as we have most |P′_{x}| such classes). Thus Γ_{x} covers at least \frac{n}{2} − \frac{n}{4} = \frac{n}{4} indices.

Each class of P′_{x} is uniquely identified by the corresponding set of at most 2k(n) intervals in which the indices of the class are read. Hence we may bound the number of classes in P′_{x} by the number of ways to choose up to 2k(n) intervals from 9k^{2}(n),

|P′_{x}| ≤ ∑_{i=0}^{2k(n)} \binom{9k^{2}(n)}{i}
= 2^{9k^{2}(n)H( \frac{2}{9k(n)} )− \frac{1}{2} lg 9k^{2}(n)+O(1)}
≤ k(n)^{3k(n)},

according to [GKP94, p. 492]^{4}, H(m) is the entropy function m lg \frac{1}{m} + (1 − m) lg \frac{1}{1−m}. By the lower bound on the size of the classes in Γ_{x} we have proved (7).

We will now prove (8); in fact we will prove the stronger statement that

∀W_{1} ∈ Γ_{x} ∃W_{2} ∈ Γ_{x} : intervals(x, W_{1}) ∩ intervals(x, W_{2}) = ∅. (9)

Since intervals(x, W_{1}) has at most 2k(n) intervals, and each such interval contains at most n/9k(n) indices, the total number of indices queried within those intervals is at most 2n/9. As there are n/4 indices covered by Γ_{x}, we can choose an index j covered by Γ_{x} that is not queried within intervals(x, W_{1}), and so the class W_{2} ∈ Γ_{x} containing j satisfies (9). This in turn imply (8).

To conclude the proof we will use Γ_{x} to construct a hard set. For each x ∈ U^{n} with D_{Δ}(x) = “NO” let W_{1} and W_{2} be the set of indices whose existence is promised in (8), and let T_{i} = intervals(x, W_{i}). Define H_{A}^{x} to be the set of y ∈ U^{n} that satisfy,

• D_{Δ}(x) = “NO”.

• T_{i} = intervals(y, W_{i}) (= intervals(x, W_{i})), hence W_{i} is a class of both Γ_{x} and Γ_{y}.

• state(x, T_{i}) = state(y, T_{i}). Define F_{i} to be a function that given x and T_{i} lists state(x, I_{ij}) where T_{i} is comprised of ∪_{j}I_{ij}; F_{i} gives an ordered lists of the states of A each time we leave T_{i}.

The above is a hard set as (7) means that |W_{i}| ≥ μ(n)·n as required, and the indices of W_{i} are certainly not read in T_{j}, in fact they are only read in T_{i}.

4These estimates are not correct for k(n) ∈ O(1), in which case we can just use Ajtai’s original estimate. Also, using \binom{n}{k} < ( \frac{n}{e})^{k} gives a bound that is almost as good, but we use the above estimate to emphasize that significantly better estimates are not possible.

Each hard set H_{A}^{x} is uniquely determined by the six-tuple ⟨W_{1}, W_{2}, T_{1}, T_{2}, F_{1}, F_{2}⟩. If we can choose this six-tuple in at most h(n) ways, there must be an x such that |H_{A}^{x}| ≥ \frac{ζ(n)|U|^{n}}{h(n)} as there are at least ζ(n)|U|^{n} inputs x with D_{Δ}(x) = “NO”.

Observe that W_{i} need not be bigger than μ(n)·n; if we have more indices than this, just take the first μ(n) · n. This may collapse a number of classes into one, meaning that we may choose each class W_{i} in \binom{n}{μ(n)·n} ways. This restriction on the size of W_{i} significantly increases the size of the interval in which we can obtain a bound.

As T_{i} consists of at most 2k(n) out of 9k(n) intervals, the number of ways to choose T_{i} is bounded by (9k(n))^{2k(n)} = (3k(n))^{4k(n)} (actually a better estimate should be possible, but it will not improve the result significantly). Finally, as T_{i} consists of at most 2k(n) intervals we fix the state of our computation in at most this many places, each with 2^{S(n)} choices, meaning that F_{i} can be chosen in at most (2^{S(n)})^{2k(n)} ways. In total we get that

h(n) ≤ \binom{n}{μ(n)·n}^{2} · ((3k(n))^{4k(n)})^{2} · ((2^{S(n)})^{2k(n)})^{2}

= (\binom{n}{μ(n) · n}^{2} (3k(n))^{8k(n)} 2^{4k(n)S(n)}.
□

Proof of Theorem 2: Let Δ be a λ(n)−full and ζ(n)−sparse relation on U. Assume that A is an R-way branching program deciding D_{Δ} on U^{n} in time k(n)·n and space S(n), such that (2) and (3) but not (4) holds. Based on these assumptions our aim is to arrive at a contradiction, thus proving the theorem. Specifically we will show that there exists an input x_{fail} such that D_{Δ}(x_{fail}) = “YES”, but the branching program answers A(x_{fail}) = “NO”.

Combining Lemma 1 and Lemma 2 we see that we can find x_{fail} if

\frac{ζ(n)|U|^{n}}{\binom{n}{μ(n)·n}^{2} (3k(n))^{8k(n)} 2^{4k(n)S(n)}} > 4λ(n)^{μ(n)·n}|U|^{n}.

Using Stirling’s approximation for n! (see eg. [Knu97, p. 115]) we get that

lg \binom{n}{μ(n)n} < 3μ(n)n lg \frac{1}{μ(n)}

for n sufficiently large, it is sufficient that

2 + lg \frac{1}{ζ(n)} + 6μ(n)n lg \frac{1}{μ(n)} + 8k(n) lg 3k(n) + 4k(n)S(n) < μ(n)n lg \frac{1}{λ(n)}.

If k(n) < n (which it will be) then 8k(n) lg 3k(n) + 4k(n)S(n) < 12k(n)S(n) as S(n) > lg n (necessarily). Likewise the constant 2 is dominated by k(n)S(n). Hence, the above is satisfied if

lg \frac{1}{ζ(n)} + 6μ(n)n lg \frac{1}{μ(n)} + 13k(n)S(n) < μ(n)n lg \frac{1}{λ(n)}.

This certainly holds if each of the three terms on the left hand side is less than a third of the term on the right hand side. We have the desired x_{fail} if

6μ(n)n lg \frac{1}{μ(n)} < \frac{1}{3}μ(n)n lg \frac{1}{λ(n)},
lg \frac{1}{ζ(n)} < \frac{1}{3}μ(n)n lg \frac{1}{λ(n)},
13k(n)S(n) < \frac{1}{3}μ(n)n lg \frac{1}{λ(n)}.

Which is implied by (2), (3) and ¬(4), since μ(n) = k(n)^{−4k(n)}. The last equation—implied by ¬(4)—holds as k(n) ≥ 1, because we must always use time n. □

7 Randomization

Definition 6 (Randomized R-way branching program) A randomized Rway branching program using r random bits, consists of a collection of 2^{r} deterministic R-way branching programs. Each execution of the randomized branching program starts by uniformly at random choosing one of the 2^{r} deterministic programs which is then executed.

We say that a randomized R-way branching program A deciding a problem D has constant 1-sided error if for 0 ≤ ϵ < \frac{1}{2} the following holds^{5}

• If D(x) = “YES”1 then our randomized branching program A answers correctly on input x.

• If D(x) = “NO” then Pr[A(x) = “NO”] > 1−ϵ.

□

Corollary 3 The statement of Theorem 2 holds for randomized R-way branching programs with constant 1-sided error if we modify the constants slightly.

Proof: By a standard averaging argument, one of the 2^{r} deterministic branching programs must correctly answer “NO” for at least a 1−ϵ fraction of the inputs with answer “NO”. Apply Theorem 2 to this deterministic branching program computing D_{Δ}. Hence we only reduce the size of our hard set with a factor ϵ. □

8 Acknowledgement

I would like to thank Faith Fich. I would also like to thank the anonymous referees for many helpful comments. In particular one referee has provided detailed suggestions on how to improve presentation as well as advice on how to make some of the proofs simpler and more precise.

5Note that that the the standard definition for 1-sided error (e.g. the complexity class RP)

allows for error on the accepting answer D(x) = “YES”, whereas our definition allows error on the rejecting answer (corresponding to CoRP).

References

[Ajt99a] Miklós Ajtai, A Non-linear Time Lower Bound for Boolean Branching Programs, 40th Annual Symposium on Foundations of Computer Science, IEEE, 1999.

[Ajt99b] , Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions, Thirty-First ACM Symposium on Theory of Computing, ACM, 1999.

[BC82] Allan Borodin and Stephen Cook, A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation, SIAM Journal on Computing 11 (1982), no. 2, 287–297.

[Bea91] Paul Beame, A General Sequential Time-Space Tradeoff for Finding Unique Elements, SIAM Journal on Computing 20 (1991), 270–277.

[BFK^{+}81] Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa, A Time-Space Tradeoff for Sorting on Non-Oblivious Machines, Journal of Computer and System Sciences 22 (1981), 351–364.

[BFMadH^{+}87] Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, and Avi Wigderson, A Time-Space Tradeoff for Element Distinctness, SIAM Journal on Computing 16 (1987), 97–99.

[BSSV00] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee, Superlinear time-space tradeoff lower bounds for randomized computation, Tech. Report TR00-25, Electronic Colloquium on Computational Complexity, 2000.

[BSSV03] , Time-space trade-off lower bounds for randomized computation of decision problems, Journal of the ACM 50 (2003), no. 2, 154–195.

[BST98] Paul Beame, Michael Saks, and Jayram S. Thathachar, Time-Space Tradeoffs for Branching Programs, 39th Annual Symposium on Foundations of Computer Science, IEEE, 1998.

[GKP94] Ronald Lewis Graham, Donald Erwin Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley, 1994.

[Hag98] Torben Hagerup, Sorting and Searching on the Word RAM, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS ’98), Lecture Notes in Computer Science, vol. 1373, Springer-Verlag, 1998, pp. 366–398.

[Kar86] Mauricio Karchmer, Two Time-Space Tradeoffs for Element Distinctness, Theoretical Computer Science 47 (1986), 237–246.

[Knu97] Donald Ervin Knuth, Fundamental Algorithms, 3rd ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1997.

[Knu98] , Sorting and Searching, 2nd ed., The Art of Computer Programming, vol. 3, Addison-Wesley, 1998.

[MNT93] Yishay Mansour, Noam Nisan, and Prasoon Tiwari, The Computational Complexity of Universal Hashing, Theoretical Computer Science (1993), no. 107, 121–133.

[Pag00] Jakob Pagter, On Ajtai’s Lower Bound Technique for r-way Branching Programs and the Hamming Distance Problem, Tech. Report BRICS-RS-01-2, BRICS, Department of Computer Science, University of Aarhus, May 2000.

[Pag01] , Time-Space Trade-Offs, Ph.D. thesis, BRICS, Department of Computer Science, University of Aarhus, 2001.

[Sav98] John Edmund Savage, Models of Computation, Addison-Wesley, 1998.

[Yao94] Andrew Chi-Chih Yao, Near-optimal Time-Space Tradeoff for Element Distinctness, SIAM Journal on Computing 23 (1994), 966–975.