Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 104-116
Citer cet article
S. A. Norin. A polynomial lower bound for the size of any $k$-min-wise independent set of permutations. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 104-116. http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a5/
@article{ZNSL_2001_277_a5,
author = {S. A. Norin},
title = {A polynomial lower bound for the size of any $k$-min-wise independent set of permutations},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {104--116},
year = {2001},
volume = {277},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a5/}
}
TY - JOUR
AU - S. A. Norin
TI - A polynomial lower bound for the size of any $k$-min-wise independent set of permutations
JO - Zapiski Nauchnykh Seminarov POMI
PY - 2001
SP - 104
EP - 116
VL - 277
UR - http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a5/
LA - ru
ID - ZNSL_2001_277_a5
ER -
%0 Journal Article
%A S. A. Norin
%T A polynomial lower bound for the size of any $k$-min-wise independent set of permutations
%J Zapiski Nauchnykh Seminarov POMI
%D 2001
%P 104-116
%V 277
%U http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a5/
%G ru
%F ZNSL_2001_277_a5
The notion of $k$-min-wise independent set of permutations, which was introduced by A. Broder et al., is considered. A nontrivial polynomial lower bound for the smallest size of such sets is obtained.
