Hamming ball

Hamming balls centered at the string "cab" with radius 1 (orange vertices and center), 2 (previous ball plus yellow vertices) and 3 (previous plus gray vertices).

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|x| of strings of the same length as x, and it is a proper subset whenever r<|x|. 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 2r+1 balls has a common intersection, then the whole family has a common intersection.

References

  1. ↑ Calabi, L.; Hartnett, W. E. (1969), "Some general results of coding theory with applications to the study of codes for the correction of synchronization errors", Information and Control, 15 (3): 235–249, doi:10.1016/S0019-9958(69)90442-2, MR 0261997
  2. 1 2 Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe (2002), "A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search", Theoretical Computer Science, 289 (1): 69–83, doi:10.1016/S0304-3975(01)00174-8, MR 1932890
  3. ↑ Alon, Noga; Jin, Zhihan; Sudakov, Benny (2024), The Helly number of Hamming balls and related problems, arXiv:2405.10275