Gap-Hamming problem
id:
gap-hamming-problem-288-2943277
title:
Gap-Hamming problem
text:
In communication complexity, the gap-Hamming problem asks, if Alice and Bob are each given a string, what is the minimal number of bits that they need to exchange in order for Alice to approximately compute the Hamming distance between their strings. The solution to the problem roughly states that, if Alice and Bob are each given a string, then any communication protocol used to compute the Hamming distance between their strings does (asymptotically) no better than Bob sending his whole string t
brand slug:
wiki
category slug:
encyclopedia
description:
Problem in communication complexity theory
original url:
https://en.wikipedia.org/wiki/Gap-Hamming_problem
date created:
date modified:
2023-02-01T01:36:07Z
main entity:
{"identifier":"Q65045178","url":"https://www.wikidata.org/entity/Q65045178"}
image:
fields total:
13
integrity:
14