Chicago Journal of Theoretical Computer Science

Volume 2005 Abstracts

  1. On Ajtai's Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem by 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]).

[] Volume 2002 Abstracts
[back] Volume 2002 [back] Published articles
[CJCTS home]

Janos Simon