On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem

Forfattere

  • Jakob Pagter

DOI:

https://doi.org/10.7146/brics.v7i11.20138

Resumé

In this report we study the proof employed by Miklos Ajtai
[Determinism versus Non-Determinism for Linear Time RAMs
with Memory Restrictions, 31st Symposium on Theory of
Computation (STOC), 1999] when proving a non-trivial lower bound
in a general model of computation for the Hamming Distance
problem: given n elements: decide whether any two of them have
"small" Hamming distance. Specifically, Ajtai was able to show
that any R-way branching program deciding this problem using
time O(n) must use space Omega(n lg n).
We generalize Ajtai's original proof allowing us to prove a
time-space trade-off for deciding the Hamming Distance problem
in the R-way branching program model for time between n
and alpha n lg n / lg lg 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 / lg lg n).

Downloads

Publiceret

2000-01-11

Citation/Eksport

Pagter, J. (2000). On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem. BRICS Report Series, 7(11). https://doi.org/10.7146/brics.v7i11.20138

Nummer

Nr. 11 (2000): RS-11 On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).