Lesson plan

Hamming ball

In combinatorics, a Hamming ball is a metric ball for Hamming distance. The Hamming ball of radius r centered at a string x over some alphabet (often the alphabet {0,1}) is the set of all strings of the same length that differ from x in at most r positions. This may be denoted using the standard notation for metric balls, B(x,r) . For an alphabet X and a string x , the Hamming ball is a subset of the Hamming space X^ of strings of the same length as x , and it is a proper subset whenever r . The name Hamming ball comes from coding theory, where error correction codes can be defined as having disjoint Hamming balls around their codewords, and covering codes can be defined as having Hamming balls around the codeword whose union is the whole Hamming space. Some local search algorithms for SAT solvers such as WalkSAT operate by using random guessing or covering codes to find a Hamming ball that contains a desired solution, and then searching within this Hamming ball to find the solution. A version of Helly's theorem for Hamming balls is known: For Hamming balls of radius r (in Hamming spaces of dimension greater than r ), if a family of balls has the property that every subfamily of at most 2^{r+1} balls has a common intersection, then the whole family has a common intersection.

Back to article

Article summary

In combinatorics, a Hamming ball is a metric ball for Hamming distance. The Hamming ball of radius r centered at a string x over some alphabet (often the alphabet {0,1}) is the set of all strings of the same length that differ from x in at most r positions. This may be denoted using the standard notation for metric balls, B(x,r) . For an alphabet X and a string x , the Hamming ball is a subset of the Hamming space X^ of strings of the same length as x , and it is a proper subset whenever r . The name Hamming ball comes from coding theory, where error correction codes can be defined as having disjoint Hamming balls around their codewords, and covering codes can be defined as having Hamming balls around the codeword whose union is the whole Hamming space. Some local search algorithms for SAT solvers such as WalkSAT operate by using random guessing or covering codes to find a Hamming ball that contains a desired solution, and then searching within this Hamming ball to find the solution. A version of Helly's theorem for Hamming balls is known: For Hamming balls of radius r (in Hamming spaces of dimension greater than r ), if a family of balls has the property that every subfamily of at most 2^{r+1} balls has a common intersection, then the whole family has a common intersection.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.