On the lower bound for parallel string matching
Clive N. Galley · International Journal of Computer Mathematics · 1994
This paper shows a string length improvement to the O(loglogm) lower bound on the number of rounds needed to find occurrences of a pattern half the length of a text string. m in Breslauer/GahTs result [BG], the previous lower bound was 5.075-1035 Here it is shown that there is a lower bound for the same constant for all m ≥248. For increasing m the constant can be improved. Given the lower bound for hashing in [GMW] the algorithm in [C] cannot be implemented in 0(1) time and for m ≥248 the algorithm cannot be implemented in 0(log∗ m) time.