Decoding frequency permutation arrays under Chebyshev distance

Abstract—A frequency permutation array (FPA) of length and distance is a set of permutations on a multiset over symbols, where each symbol appears exactly times and the dis-tance between any two elements in the array is at least. FPA generalizes the notion of permutation array. In this paper, under the Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabil-ities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most sym-bols, which has an interesting application to private information retrieval. Index Terms—Chebyshev distance, frequency permutation array (FPA), locally decodable code, permanent, permutation array (PA). I