**On Ajtai's Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem**by Jakob Pagter.

28 May 2005Miklos 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]).

Volume 2002 Abstracts

Volume 2002 Published articles

Janos Simon