Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets $$\mathcal{B}$$ and $$\mathcal{G}$$ of strings of length L with characters from an unbounded alphabet Σ, i.e., the size of Σ is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of $$\mathcal{B}$$ is a string that minimizes the maximum of Hamming1 distance(s, s*) over all string s : s ∈ $$\mathcal{B}$$ . In contrast, a farthest string t* from $$\mathcal{G}$$ maximizes the minimum of Hamming distance(t*,t) over all elements t: t ∈ $$\mathcal{G}$$ . A distinguisher of $$\mathcal{B}$$ from $$\mathcal{G}$$ is a string that is close to every string in $$\mathcal{B}$$ and far away from any string in $$\mathcal{G}$$ . We obtain polynomial time approximation schemes to settle the above problems.