The communication complexity of gap Hamming distance

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

Authors: 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

Recommendations

• The communication complexity of the Hamming distance problem
• Communication Complexity of Computing the Hamming Distance
• One-sided error communication complexity of gap Hamming distance
• The one-way communication complexity of Hamming distance
• The information complexity of Hamming distance
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• The intractability of computing the Hamming distance

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 (25)

• Two Party Distribution Testing: Communication and Security
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Arthur-Merlin streaming complexity
• The communication complexity of the Hamming distance problem
• The communication complexity of functions with large outputs
• The information complexity of Hamming distance
• Rectangles are nonnegative juntas
• The one-way communication complexity of Hamming distance
• Anticoncentration and the Exact Gap-Hamming Problem
• Title not available (Why is that?)
• Communication Complexity of Computing the Hamming Distance
• Sketching and embedding are equivalent for norms
• Interactive information complexity
• Query-to-communication lifting for BPP
• Title not available (Why is that?)
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• Communication and information complexity
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Lifting Theorems for Equality
• Lower bounds on information complexity via zero-communication protocols and applications
• Low correlation noise stability of symmetric sets
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• One-sided error communication complexity of gap Hamming distance
• Communication complexity with small advantage

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)