Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

DOI10.1007/978-3-642-32512-0_30MaRDI QIDQ3167409zbMATH OpenOpenAlexFDO

Authors Noga Alon, Shachar Lovett

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_30

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Recommendations

• Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• Simple permutations mix well

Cited in

(9)

• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Probabilistic existence of regular combinatorial structures
• A recursive construction of t-wise uniform permutations
• Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
• Exploiting dense structures in parameterized complexity
• Low-memory algorithms for online edge coloring
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Automata, Languages and Programming

This page was built for publication: Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions

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