# Covering radius of a code in the Hamming space

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

I have read this paper and I couldn't understand how to culculate the $$covering$$ $$radius$$ of a code in the Hamming space. It is defined as follows in the paper.

We identify assignments with binary words. The set of these words of length $$n$$ is the $$Hamming$$ $$space$$ denoted by $$H_n=\{0,1\}^n$$. The $$Hamming$$ $$distance$$ between two assignments is the number of positions in which these two assignments differ. The $$ball$$ of radius $$r$$ around an assignment $$a$$ is the set of all assignments whose Hamming distance to $$a$$ is at most $$r$$.
A $$code$$ of length $$n$$ is simply a subset of $$H_n$$. The $$covering$$ $$radius$$ $$r$$ of a code $$C$$ is defined by $$r=\max_{u∈\{0,1\}^n}\min_{v∈C }d(u,v),$$ where $$d(u,v)$$ denotes the Hamming distance between $$u$$ and $$v$$.

The $$\max$$ of $$\min$$ is exactly the point I couldn't calculate. So I considered the instance of $$C$$ and tried to calculate its covering radius.

e.g.)$$C=\{000,010,011,100,101,110\}⊆H_3$$

In this case, how can I calculate the covering radius $$r$$?

• Note you should use *asterisks* to typeset italics in this site (instead of hacking it with LaTeX). – dkaeae Jul 8 '19 at 7:43
• I didn't know that. I'm sorry for not knowing it. I'll use asterisks from now on. – NEUTRON Jul 8 '19 at 8:31

It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is max(1,1)=1
• for each possible code x, find the closest element c in C (i.e. the one with minimum distance d(x,c)) and record this distance