#

### 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]).