On linear hashing of binary sets (Q1280345)

The main result of the paper is as follows. For any \(k\) let the inequality \[ 2^{k+1} - k - 2> \tfrac 12 m(m-1) \] be satisfied, where \(m=O(n^p)\) has polynomial growth. Then there exists a linear hashing operator \(\mathcal H\) with the scheme realization complexity \[ l(\mathcal H)\lesssim 2p(n-2p\log n)\log n, \] which can be efficiently constructed.