A derandomization using min-wise independent permutations

DOI10.1016/S1570-8667(03)00003-0zbMath1118.68580OpenAlexW2066097866MaRDI QIDQ876688

Moses Charikar, Andrei Z. Broder, 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

parallel algorithmsderandomizationset covermin-wise independence

Mathematics Subject Classification ID

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

Related Items (6)

Interval selection in the streaming model ⋮ Unnamed Item ⋮ Min-wise independent groups ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation ⋮ Exponential time improvement for min-wise based algorithms

Cites Work

• Universal classes of hash functions
• Randomized geometric algorithms and pseudorandom generators
• Simple Constructions of Almost k-wise Independent Random Variables
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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