Pairwise independence and derandomization.

MaRDI QIDQ3413301zbMATH OpenFDO

Authors Michael Luby, A. Wigderson

Publication date 4 January 2007

zbMATH Keywords

unconditional derandomization

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Can every randomized algorithm be derandomized?
• scientific article; zbMATH DE number 1857655
• Randomness – A Computational Complexity Perspective
• A primer on pseudorandom generators
• scientific article; zbMATH DE number 1789922

Cited in

(16)

• Min-wise independent permutations
• Protocols for asymmetric communication channels
• A note on the price of bandit feedback for mistake-bounded online learning
• Scheduling split intervals with non-uniform demands
• New bounds on the price of bandit feedback for mistake-bounded online multiclass learning
• Pairwise Independence and Derandomization
• Generalization properties of hyper-RKHS and its applications
• Partially independent random variables
• On discrete stochastic processes with disjunctive outcomes
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• Tight Probability Bounds with Pairwise Independence
• Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning
• Pricing commodities
• Derandomization of quantum algorithm for triangle finding
• Pairwise independent correlation gap
• A derandomization using min-wise independent permutations

This page was built for publication: Pairwise independence and derandomization.

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