A derandomization using min-wise independent permutations

DOI10.1016/S1570-8667(03)00003-0MaRDI QIDQ876688zbMATH OpenOpenAlexFDO

Authors Andrei Broder, Moses Charikar, Michael Mitzenmacher

Publication date 26 April 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1570-8667(03)00003-0

zbMATH Keywords

derandomizationparallel algorithmsset covermin-wise independence

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms in computer science (68W99)

Recommendations

• scientific article; zbMATH DE number 1445297
• On (ε,k)‐min‐wise independent permutations
• Publication:4952611
• scientific article; zbMATH DE number 1418262
• Min-wise independent permutations

Cites work

• scientific article; zbMATH DE number 1615265 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1305436 (Why is no real title available?)
• scientific article; zbMATH DE number 1775418 (Why is no real title available?)
• Pairwise independence and derandomization.
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Randomized geometric algorithms and pseudorandom generators
• Simple Constructions of Almost k-wise Independent Random Variables
• Universal classes of hash functions

Cited in

(8)

• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• scientific article; zbMATH DE number 1418262 (Why is no real title available?)
• Exponential time improvement for min-wise based algorithms
• An efficient distributed algorithm for constructing small dominating sets
• Min-wise independent groups
• Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation
• Using Rademacher permutations to reduce randomness

This page was built for publication: A derandomization using min-wise independent permutations

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