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

### 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 / lg 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 / lg lg n).

Published

2000-01-11

How to Cite

*BRICS Report Series*,

*7*(11). https://doi.org/10.7146/brics.v7i11.20138

Section

Articles

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.