Porat and Porat [FOCS 2009] described the first efficient randomised algorithm for the pattern matching problem in the streaming model, using \(\mathcal {O}(\log {m} \log {n})\) bits for a text of length n and a pattern of length m, against the lower bound of \(\varOmega (\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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Two-Player Communication Complexity of Pattern Matching

  • Paweł Gawrychowski,
  • Wojciech Janczewski

摘要

Porat and Porat [FOCS 2009] described the first efficient randomised algorithm for the pattern matching problem in the streaming model, using \(\mathcal {O}(\log {m} \log {n})\) bits for a text of length n and a pattern of length m, against the lower bound of \(\varOmega (\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.