Miklos Ajtai in "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 Omega(n lg n).

We extend the proof to obtain a time-space trade-off for time between n and alpha n (lg n / lglg 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 \ lglg n]).