The communication complexity of gap Hamming distance

DOI10.4086/TOC.2012.V008A008zbMATH Open1253.68158OpenAlexW2122058331MaRDI QIDQ2913808FDOQ2913808

Alexander A. Sherstov

Publication date: 27 September 2012

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2012.v008a008

zbMATH Keywords

communication complexityTalagrand's concentration inequalitygap Hamming distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• On the distributional complexity of disjointness

Cited In (20)

• Two Party Distribution Testing: Communication and Security
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Arthur-Merlin streaming complexity
• Query-to-Communication Lifting for BPP
• Interactive Information Complexity
• The communication complexity of functions with large outputs
• Rectangles are nonnegative juntas
• Anticoncentration and the Exact Gap-Hamming Problem
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Communication Complexity of Statistical Distance
• One-Sided Error Communication Complexity of Gap Hamming Distance.
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• Communication and information complexity
• Sketching and Embedding are Equivalent for Norms
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Lifting Theorems for Equality
• Low correlation noise stability of symmetric sets
• Communication complexity with small advantage

Recommendations

• Title not available (Why is that?) 👍 👎
• The communication complexity of the Hamming distance problem 👍 👎
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance 👍 👎
• The intractability of computing the Hamming distance 👍 👎
• Communication Complexity of Computing the Hamming Distance 👍 👎
• The Information Complexity Of Hamming Distance 👍 👎
• Communication Complexity of Statistical Distance 👍 👎
• Communication Complexity of Statistical Distance 👍 👎
• One-Sided Error Communication Complexity of Gap Hamming Distance. 👍 👎

This page was built for publication: The 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 Q2913808)