| Attributes | Values |
|---|
| rdf:type
| |
| Description
| - Rodina permutací $F \subseteq S_n$ s daným pravděpodobnostním rozdělením se nazývá 'k-restricted min-wise independent', pokud platí $Pr[min \pi(X) = \pi(x)] = 1/|X|$ pro libovolnou podmnožinu $X \subseteq [n]$ splňující $|X| l.e. k$, libovolné $x\in X$, a náhodně zvolené $\pi\in F$. Ukážeme jednoduchý důkaz Norinova výsledku, že každá taková rodina má velikost aspoň $\binom{n-1}{\lceil k-1/2\rceil}$. Nejlepší známý dolní odhad na velikost takové rodiny je $1 + \Sum_{j=2}^k (j - 1)\binom{n}{j}$. Ukážeme, že tento odhad je těsný, pokud je snahou napodobit nikoliv rovnoměrné rozdělení na $S_n$, ale rozdělení určené prioritami prvků $[n]$. Zkoumáme také případy, kdy se podmínka na nezávislost vyžaduje pouze pro množiny $X$ velikosti přesně $k$ (kdy máme pouze dolní odhad $\Omega(log log n + k)$) a pro množiny velikosti $k$ a $k - 1$ (kdy získáme dolní odhad $n - k + 2$). (cs)
- A family of permutations $F \subseteq S_n$ with a probability distribution on it is called k-restricted min-wise independent if we have $Pr[min \pi(X) = \pi(x)] = 1/|X|$ for every subset $X \subseteq [n]$ with $|X|l.e. k$, every $x\in X$, and $\pi\in F$ chosen at random. We present a simple proof of a result of Norin: every such family has size at least $\binom{n-1}{\lceil k-1/2\rceil}$. The best available upper bound for the size of such family is $1 + \Sum_{j=2}^k (j - 1)\binom{n}{j}$. We show that this bound is tight if the goal is to imitate not the uniform distribution on $S_n$, but a distribution given by assigning suitable priorities to the elements of $[n]$. We also investigate the cases where the min-wise independence condition is required only for sets $X$ of size exactly $k$ (where we have only an $\Omega(log log n + k)$ lower bound), or for sets of size $k$ and $k - 1$ (where we already obtain a lower bound of $n - k + 2$).
- A family of permutations $F \subseteq S_n$ with a probability distribution on it is called k-restricted min-wise independent if we have $Pr[min \pi(X) = \pi(x)] = 1/|X|$ for every subset $X \subseteq [n]$ with $|X|l.e. k$, every $x\in X$, and $\pi\in F$ chosen at random. We present a simple proof of a result of Norin: every such family has size at least $\binom{n-1}{\lceil k-1/2\rceil}$. The best available upper bound for the size of such family is $1 + \Sum_{j=2}^k (j - 1)\binom{n}{j}$. We show that this bound is tight if the goal is to imitate not the uniform distribution on $S_n$, but a distribution given by assigning suitable priorities to the elements of $[n]$. We also investigate the cases where the min-wise independence condition is required only for sets $X$ of size exactly $k$ (where we have only an $\Omega(log log n + k)$ lower bound), or for sets of size $k$ and $k - 1$ (where we already obtain a lower bound of $n - k + 2$). (en)
|
| Title
| - On restricted min-wise independence of permutations
- On restricted min-wise independence of permutations (en)
- O omezené nezávislosti permutací vzhledem k minimům (cs)
|
| skos:prefLabel
| - On restricted min-wise independence of permutations
- On restricted min-wise independence of permutations (en)
- O omezené nezávislosti permutací vzhledem k minimům (cs)
|
| skos:notation
| - RIV/00216208:11320/03:00005529!RIV08-MSM-11320___
|
| http://linked.open.../vavai/riv/strany
| |
| http://linked.open...avai/riv/aktivita
| |
| http://linked.open...avai/riv/aktivity
| - P(LN00A056), Z(MSM 113200005)
|
| http://linked.open...iv/cisloPeriodika
| |
| http://linked.open...vai/riv/dodaniDat
| |
| http://linked.open...aciTvurceVysledku
| |
| http://linked.open.../riv/druhVysledku
| |
| http://linked.open...iv/duvernostUdaju
| |
| http://linked.open...titaPredkladatele
| |
| http://linked.open...dnocenehoVysledku
| |
| http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/03:00005529
|
| http://linked.open...riv/jazykVysledku
| |
| http://linked.open.../riv/klicovaSlova
| - restricted; min-wise; independence; permutations (en)
|
| http://linked.open.../riv/klicoveSlovo
| |
| http://linked.open...odStatuVydavatele
| - US - Spojené státy americké
|
| http://linked.open...ontrolniKodProRIV
| |
| http://linked.open...i/riv/nazevZdroje
| - Random Structures and Algorithms
|
| http://linked.open...in/vavai/riv/obor
| |
| http://linked.open...ichTvurcuVysledku
| |
| http://linked.open...cetTvurcuVysledku
| |
| http://linked.open...vavai/riv/projekt
| |
| http://linked.open...UplatneniVysledku
| |
| http://linked.open...v/svazekPeriodika
| |
| http://linked.open...iv/tvurceVysledku
| |
| http://linked.open...n/vavai/riv/zamer
| |
| issn
| |
| number of pages
| |
| http://localhost/t...ganizacniJednotka
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)