.png){kind=icon}
.png){kind=icon}
Return
Two-Player Communication Complexity of Pattern Matching
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_13.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Porat and Porat [FOCS 2009] described the first efficient randomised algorithm for the pattern matching problem in the streaming model, using O( log m log n) bits for a text of length n and a pattern of length m, against the lower bound of O(log n) bits. Since then, multiple papers considered many variants of this problem, but with virtually no progress on the lower bounds side, leaving a logarithmic gap in the space complexity for the very basic variant. We discuss a modification of the lower bound of Ergun, Jowhari, and Saglam [RANDOM 2010] against a restricted class of algorithms for the streaming pattern matching problem. Then, we show that the standard approach via communication complexity does not suffice to obtain a better lower bound, by presenting an efficient communication protocol.
Keywords:
Pattern matching
Streaming
Communication complexity
Journal
S
IF:
0
Papers:
22
Citations:
0