Geodesic
On linear operators injective on arbitrary subsets
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 132-141 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{UZKU_2014_156_3_a13,
     author = {A. V. Chashkin},
     title = {On linear operators injective on arbitrary subsets},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {132--141},
     year = {2014},
     volume = {156},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a13/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On linear operators injective on arbitrary subsets
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 132
EP  - 141
VL  - 156
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a13/
LA  - ru
ID  - UZKU_2014_156_3_a13
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On linear operators injective on arbitrary subsets
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 132-141
%V 156
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a13/
%G ru
%F UZKU_2014_156_3_a13
A. V. Chashkin. On linear operators injective on arbitrary subsets. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 132-141. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a13/

[1] Andreev A. E., Bolotov A. A., “O lineinom kheshirovanii dvoichnykh mnozhestv”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekhanika, 1997., no. 2, 22–25 | MR | Zbl

[2] Goppa V. D., “Kody i informatsiya”, Usp. matem. nauk, 39:1 (1984), 77–120 | MR | Zbl

[3] Krichevskii R. E., Szhatie i poisk informatsii, Radio i svyaz, M., 1989, 168 pp. | MR

[4] Lozhkin S. A., Semenov A. A., “Ob odnom metode szhatiya informatsii i o slozhnosti realizatsii monotonnykh simmetricheskikh funktsii”, Izv. vuzov. Matem., 1988, no. 7, 44–52 | MR | Zbl

[5] Chashkin A. V., “Lokalnaya slozhnost bulevykh funktsii”, Diskretnyi analiz i issled. oper. Ser. 1, 4:3 (1997), 69–80 | MR | Zbl

[6] Chashkin A. V., “Sovershennoe lineinoe kheshirovanie v bulevom kube”, Diskretnaya matematika i ee prilozheniya, Sb. lektsii, Vyp. 5, IPM RAN, M., 2009, 56–67

[7] Andersson A., Miltersen P. B., Riis S., Thorup M., “Static dictionaries on AC$^0$ RAMs: Query time $\Theta(\sqrt{p\log n/\log\log n})$ is necessary and sufficient”, FOCS, 36th IEEE Symposium on Foundations of Computer Science (FOCS), 1996, 441–459 | MR

[8] Goldreich O., Wigderson A., On the Circuit Complexity of Perfect Hashing, ECCC TR96-041, URL: , 1996, svobodnyi http://eccc.hpi-web.de/report/1996/041/

[9] Miltersen P. B., “Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries”, Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA' 98), 1998, 556–563 | MR | Zbl

[10] Gelfand S. I., Dobrushin R. L., Pinsker M. S., “On the complexity of coding”, Second Int. Symposium on Information Theory, Akademiai Kiado, Budapest, 1973, 177–184

[11] Sudan M., Essential Coding Theory, URL: , svobodnyi http://people.csail.mit.edu/~madhu/FT02/

[12] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v 2 t., v. 1, Mir, M., 1984, 528 pp. | MR | Zbl