Chicago Journal of Theoretical Computer Science

Volume 2005

Article 1

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

Jakob Pagter
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 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]).

DOI: 10.4086/cjtcs.2005.001
[] Volume 2002, Article [] Article 2
[back] Volume 2002 [back] Published articles
[CJCTS home]