Abstract:
Linear operators that are injective on subsets of a linear space over $GF(p)$ are considered. Given any positive constant $\varepsilon$ and sufficiently large $n$, for any domain $D$ from $GF^n(p)$, there exists a linear operator injective on this domain whose rank is at most $(2+\varepsilon)\log_p|D|$ and whose complexity is $\mathcal O(n)$.
Keywords:perfect linear hashing, circuits of functional elements, circuit complexity.