All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD1-S4-T3.3
Paper Title New upper bounds for (b,k)-hashing
Authors Stefano Della Fiore, Simone Costa, Marco Dalai, University of Brescia, Italy
Session D1-S4-T3: Structures & Inference
Chaired Session: Monday, 12 July, 23:00 - 23:20
Engagement Session: Monday, 12 July, 23:20 - 23:40
Abstract 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.