Min-wise independent groups

DOI10.1016/S0195-6698(03)00081-7MaRDI QIDQ1413231zbMATH OpenFDO

Authors D. Massart

Publication date 16 November 2003

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0195-6698(03)00081-7

zbMATH Keywords

Min-wise independent groupstransitive groups

Mathematics Subject Classification ID

General theory for finite permutation groups (20B05) Probabilistic methods in group theory (20P05) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Combinatorial probability (60C05)

Review text

Let \(\Omega\) be a finite set of cardinality \(n\) with a linear order on it and let \(k\) be a positive integer. Let \(F\) be a set of permutations on \(\Omega\) and let \(\Pr_{\mathcal F}\) be an arbitrary distribution of probability on \(\mathcal F\). The set \(\mathcal F\) is said to be biased \(k\)-restricted min-wise independent if for every subset \(X\) of \(\Omega\) such that \(|X|\leq k\), and every \(x\in X\), when \(\pi\) is chosen at random in \(\mathcal F\), we have that \(\Pr_\mathcal F(\min \pi(X))=\pi=1/|X|\). The authors study biased \(k\)-restricted min-wise independent groups. In particular, they prove that when \(k\) is close to \(n\), then biased \(k\)-restricted min-wise independent groups are transitive.

Recommendations

• Min-Wise Independent Families with Respect to any Linear Order
• scientific article; zbMATH DE number 2187718
• MULTIPLE TRANSITIVITY AND MIN-WISE INDEPENDENCE IN PERMUTATION GROUPS
• Automorphisms of Projective Spaces and Min-Wise Independent Sets of Permutations
• On restricted min‐wise independence of permutations

Cites work

• A derandomization using min-wise independent permutations
• A polynomial lower bound on the size of a k-min-wise independent set of permutations
• Algorithms for Sat and upper bounds on their complexity
• scientific article; zbMATH DE number 47601 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Min-wise independent permutations
• On restricted min‐wise independence of permutations
• On the sample size of k -restricted min-wise independent permutations and other k -wise distributions

Cited in

(5)

• On restricted min‐wise independence of permutations
• MULTIPLE TRANSITIVITY AND MIN-WISE INDEPENDENCE IN PERMUTATION GROUPS
• Automorphisms of Projective Spaces and Min-Wise Independent Sets of Permutations
• Min-Wise Independent Families with Respect to any Linear Order
• scientific article; zbMATH DE number 2187718 (Why is no real title available?)

This page was built for publication: Min-wise independent groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1413231)