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(s,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<|x|

. The name Hamming ball comes from coding theory, where error correction codes can be defined as having disjoint Hamming balls around their codewords,{{r|ch}} and covering codes can be defined as having Hamming balls around the codeword whose union is the whole Hamming space.{{r|ksat}}

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.{{r|ksat}}

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.{{r|ajs}}

References

{{reflist|refs=

{{citation

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Jin | first2 = Zhihan

| last3 = Sudakov | first3 = Benny | author3-link = Benny Sudakov

| arxiv = 2405.10275

| title = The Helly number of Hamming balls and related problems

| year = 2024}}

{{citation

| last1 = Calabi | first1 = L.

| last2 = Hartnett | first2 = W. E.

| journal = Information and Control

| mr = 261997

| pages = 235–249

| title = Some general results of coding theory with applications to the study of codes for the correction of synchronization errors

| volume = 15

| year = 1969| issue = 3

| doi = 10.1016/S0019-9958(69)90442-2

}}

{{citation

| last1 = Dantsin | first1 = Evgeny

| last2 = Goerdt | first2 = Andreas

| last3 = Hirsch | first3 = Edward A.

| last4 = Kannan | first4 = Ravi

| last5 = Kleinberg | first5 = Jon

| last6 = Papadimitriou | first6 = Christos

| last7 = Raghavan | first7 = Prabhakar

| last8 = Schöning | first8 = Uwe

| doi = 10.1016/S0304-3975(01)00174-8

| issue = 1

| journal = Theoretical Computer Science

| mr = 1932890

| pages = 69–83

| title = A deterministic $(2-2/(k+1))^n$ algorithm for $k$ -SAT based on local search

| volume = 289

| year = 2002}}

}}

Category:String metrics

Category:Metric geometry

Category:Coding theory