2021/01/26 by Della Fiore, Stefano, Costa, Simone, Dalai, Marco
#68R05 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2101.10916
For fixed integers b≥ k, the problem of perfect (b,k)-hashing asks for the asymptotic growth of largest subsets of \1,2,…,b\n such that for any k distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general b, k, was derived by Fredman and Komlós in the '80s and improved for certain b≠ k by Körner and Marton and by Arikan. Only very recently better bounds were derived for the general b,k case by Guruswami and Riazanov, while stronger results for small values of b=k were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to b≠ k and further strengthen the bounds for some specific small values of b and k. The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity.