Amortized communication complexity of an equality predicate

DOI10.1007/978-3-642-38536-0_19zbMATH Open1382.68119arXiv1212.1941OpenAlexW2963153038MaRDI QIDQ4928487FDOQ4928487

Authors: Vladimir Nikishkin 

Publication date: 14 June 2013

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: We study the communication complexity of a direct sum of independent copies of the equality predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); computational complexity of the proposed protocol is polynomial in size of inputs. Our protocol improves the result achieved in 1995(Feder, Kushilevitz, Naor, Nisan). Our construction is based on two techniques: Nisan's pseudorandom generator (1992) and Smith's string synchronization algorithm (2007).

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

Recommendations

• Amortized Communication Complexity
• Probabilistic communication complexity
• scientific article; zbMATH DE number 1769898
• Three results on interactive communication
• Certifying equality with limited interaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (4)

• Equality, revisited
• On the power of laconic advice in communication complexity
• Amortized Communication Complexity
• The communication complexity of set intersection and multiple equality testing

This page was built for publication: Amortized communication complexity of an equality predicate

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