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
Abstract
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]).
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Volume 2002, Article
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 2
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2002
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}