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

Jakob Pagter

May 2000

Abstract:

In this report we study the proof employed by Miklos Ajtai [Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions, 31st Symposium on Theory of Computation (STOC), 1999] when proving a non-trivial lower bound in a general model of computation for the Hamming distance problem: given $n$ elements decide whether any two of them have ``small'' Hamming distance. Specifically, Ajtai was able to show that any $R$-way branching program deciding this problem using time $O(n)$ must use space $\Omega(n\lg n)$. We generalize Ajtai's original proof allowing us to prove a time-space trade-off for deciding the Hamming distance problem in the $R$-way branching program model for time between $n$ and $\alpha n\lg n$, for some suitable $0<\alpha<1$. In particular we prove that if space is $O(n^{1-\epsilon})$, then time is $\Omega(n\lg n)$

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.