On the lower bound for parallel string matching

Abstract

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-10³⁵ Here it is shown that there is a lower bound for the same constant for all m ≥2⁴⁸. 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 ≥2⁴⁸ the algorithm cannot be implemented in 0(log∗ m) time.

Keywords:

• Analysis of algorithms
• design of algorithms
• parallel algorithms

¹The author was supported by the 91809000 Science and Engineering Research Council Postgraduate Studentship. The auther was also partially supported by a University of Lodon central research fund grant.

¹The author was supported by the 91809000 Science and Engineering Research Council Postgraduate Studentship. The auther was also partially supported by a University of Lodon central research fund grant.

Notes

¹The author was supported by the 91809000 Science and Engineering Research Council Postgraduate Studentship. The auther was also partially supported by a University of Lodon central research fund grant.