TY - JOUR AU - Pagter, Jakob PY - 2000/01/11 Y2 - 2024/03/29 TI - On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem JF - BRICS Report Series JA - BRICS VL - 7 IS - 11 SE - Articles DO - 10.7146/brics.v7i11.20138 UR - https://tidsskrift.dk/brics/article/view/20138 SP - AB - In this report we study the proof employed by Miklos Ajtai<br />[Determinism versus Non-Determinism for Linear Time RAMs<br />with Memory Restrictions, 31st Symposium on Theory of <br />Computation (STOC), 1999] when proving a non-trivial lower bound<br />in a general model of computation for the Hamming Distance<br />problem: given n elements: decide whether any two of them have<br />"small" Hamming distance. Specifically, Ajtai was able to show<br />that any R-way branching program deciding this problem using<br />time O(n) must use space Omega(n lg n).<br />We generalize Ajtai's original proof allowing us to prove a<br />time-space trade-off for deciding the Hamming Distance problem<br /> in the R-way branching program model for time between n<br />and alpha n lg n / lg lg n, for some suitable 0 < alpha < 1. In particular we prove<br />that if space is O(n^(1−epsilon)), then time is Omega(n lg n / lg lg n). ER -