论文标题
改善$（b，k）$的界限 - 哈希
Improved Bounds for $(b,k)$-hashing
论文作者
论文摘要
对于固定的整数$ b \ geq k $，在计算机科学和组合学方面具有相关兴趣的问题是确定渐近增长的$ n $，这是$ n $ n $函数的最大套装。同等地，确定$ \ {1,2，\ ldots，b \}^n $的最大子集的渐近生长，以使得对于集合中的任何$ k $不同的元素，它们都有一个不同的坐标。 弗雷德曼（Fredman）和科姆洛斯（Komlós）在80年代衍生出了一般$ b，k $的重要渐近上限，并改进了Körner和Marton以及Arikan的某些$ B \ neq K $。 Guruswami和Riazanov的一般$ B，K $ CASE才得出了更高的界限，而Arikan，Dalai，Guruswami和Radhakrishnan以及Costa和Costa and Dalai获得了Arikan，Arikan获得的少量$ B = K $。在本文中，我们俩都展示了后者的一些结果如何扩展到$ b \ neq k $，并进一步加强了一些特定的小额值$ b $和$ k $的界限。我们使用的方法取决于将优化问题减少到有限数量的情况下，表明可以通过精制参数以较高的复杂性为代价获得进一步的结果，这可以通过使用更复杂和优化的算法方法来降低。
For fixed integers $b\geq k$, a problem of relevant interest in computer science and combinatorics is that of determining the asymptotic growth, with $n$, of the largest set for which a $(b, k)$-hash family of $n$ functions exists. Equivalently, determining the asymptotic growth of a largest 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. An important asymptotic upper bound for general $b, 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 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 which could be reduced by using more sophisticated and optimized algorithmic approaches.
