| Paper ID | D1-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.
|
