New upper bounds for $(b,k)$-hashing
Autor: | Simone Costa, Marco Dalai, Stefano Della Fiore |
---|---|
Rok vydání: | 2021 |
Předmět: |
FOS: Computer and information sciences
Optimization problem Computer Science - Information Theory Information Theory (cs.IT) Hash function Information theory Upper and lower bounds 68R05 Finite element method Set (abstract data type) Combinatorics Reduction (complexity) FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) Finite set Mathematics |
Zdroj: | ISIT |
DOI: | 10.48550/arxiv.2101.10916 |
Popis: | For fixed integers $b\geq k$, the problem of perfect $(b,k)$-hashing asks for the asymptotic growth of largest subsets of $\{1,2,\ldots,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\'os in the '80s and improved for certain $b\neq k$ by K\"orner 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\neq 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. Comment: arXiv admin note: substantial text overlap with arXiv:2012.00620 |
Databáze: | OpenAIRE |
Externí odkaz: |
Pro tento záznam nejsou dostupné žádné jednotky.