ALCOMFT-TR-01-172

Jakob Pagter
On Ajtai's Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem
Århus. Work package 4. June 2001.

Abstract: Miklos Ajtai [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(nlg n).

We extend the proof to obtain a time-space trade-off for time between n and an(lg n)/(lglg n), for some suitable 0<a<1. In particular we prove that if space is O(n^1-epsilon), then time is Omega(n(lg n)/(lglg n)).

Postscript file: ALCOMFT-TR-01-172.ps.gz (109 kb).