Improved Bounds for (b, k)-Hashing

For fixed integers n and b >= k , let A(b,k,n) the largest size of a subset of {1,2, ..., 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 Komlos in the 80s and improved for certain b not equal k by Korner 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.