Compressed communication complexity of longest common prefixes

DOI10.1007/978-3-030-00479-8_7MaRDI QIDQ6109737zbMATH OpenWikidataFDO

Authors Philip Bille, Mikko Berggreen Ettienne, Roberto Grossi, Inge Li Gørtz, Eva Rotenberg

Publication date 28 July 2023

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.03102

zbMATH Keywords

longest common prefixupper boundcommunication complexitycompressionLZ77output sensitivitypredecessor

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Communication complexity, information complexity (68Q11)

Abstract: We consider the communication complexity of fundamental longest common prefix (Lcp) problems. In the simplest version, two parties, Alice and Bob, each hold a string, $A$ and $B$, and we want to determine the length of their longest common prefix $l=extLcp(A,B)$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of $A$ and $B$ is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of $z$ phrases, only $O(lgz)$ rounds and $O(lgell)$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $B_1,ldots,B_k$, and the goal is to find the length of the maximal longest prefix shared by $A$ and any of $B_1,ldots,B_k$. Here, we give a protocol with $O(logz)$ rounds and $O(lgzlgk+lgell)$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.

Recommendations

• The communication and streaming complexity of computing the longest common and increasing subsequences
• Communication complexity and combinatorial lattice theory
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Communication-Efficient Private Protocols for Longest Common Subsequence
• Communication complexity in lattices
• scientific article; zbMATH DE number 2038719
• Longest common prefixes with k-errors and applications
• scientific article; zbMATH DE number 4068270
• Lower bounds on communication complexity
• Composition theorems in communication complexity

Cited in

(1)

• Communication-Efficient Private Protocols for Longest Common Subsequence

This page was built for publication: Compressed communication complexity of longest common prefixes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109737)