On Ajtai's Lower Bound Technique for -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 elements decide whether any two of them have small'' Hamming distance. Specifically, Ajtai was able to show that any -way branching program deciding this problem using time must use space . We generalize Ajtai's original proof allowing us to prove a time-space trade-off for deciding the Hamming distance problem in the -way branching program model for time between and , for some suitable . In particular we prove that if space is , then time is

Available as PostScript, PDF, DVI.