One-sided error communication complexity of gap Hamming distance

DOI10.4230/LIPICS.MFCS.2018.7MaRDI QIDQ5005103zbMATH OpenOpenAlexFDO

Authors Egor Klenin, Alexander Kozachinskiy

Publication date 4 August 2021

Full work available at URL https://dblp.uni-trier.de/db/conf/mfcs/mfcs2018.html#KleninK18

zbMATH Keywords

communication complexitygap Hamming distanceone-sided error

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The communication complexity of gap Hamming distance
• The communication complexity of the Hamming distance problem
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• Communication Complexity of Computing the Hamming Distance
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems

Cites work

• Better Gap-Hamming Lower Bounds via Better Round Elimination
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• scientific article; zbMATH DE number 6292622 (Why is no real title available?)
• On the power of quantum fingerprinting
• Optimal space lower bounds for all frequency moments
• Property testing lower bounds via communication complexity
• Streaming algorithms with one-sided estimation
• The communication complexity of gap Hamming distance
• The communication complexity of the Hamming distance problem
• The one-way communication complexity of Hamming distance

Cited in

(4)

• The communication complexity of gap Hamming distance
• The information complexity of Hamming distance
• The communication complexity of the Hamming distance problem
• Combinatorial version of the Slepian-Wolf coding theorem for binary strings

This page was built for publication: One-sided error communication complexity of gap Hamming distance

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