Back to Search
Start Over
Improved Bounds for (b, k)-Hashing.
- Source :
- IEEE Transactions on Information Theory; Aug2022, Vol. 68 Issue 8, p4983-4997, 15p
- Publication Year :
- 2022
-
Abstract
- For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ 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 strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 68
- Issue :
- 8
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 157958035
- Full Text :
- https://doi.org/10.1109/TIT.2022.3167608