Published by Dept. CS U. Chicago. Copyright 2005 CJTCS
On Ajtai's Lower Bound Technique for R-way Branching Programs
and the Hamming Distance Problem
28 May 2005
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
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]).