Pairwise Independence and Derandomization

DOI10.1561/0400000009MaRDI QIDQ3522268zbMATH OpenOpenAlexFDO

Authors Michael Luby, A. Wigderson

Publication date 1 September 2008

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8687

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Recommendations

• Pairwise independence and derandomization.
• Independence, relative randomness, and PA degrees
• Tight Probability Bounds with Pairwise Independence
• scientific article; zbMATH DE number 3856078
• On pairyise independent and independent exchangeable random variables
• Independence in randomizations
• scientific article; zbMATH DE number 635856
• Independence tuples and Deninger's problem
• Independence, randomness and the axiom of choice

Cited in

(11)

• Parameterized random complexity
• A partial derandomization of phaselift using spherical designs
• Combinatorial auctions with conflict-based externalities
• On possible dependence structures of a set of random variables
• Tight Probability Bounds with Pairwise Independence
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• Bounds for \(c\)-ideal hashing
• Pairwise-independent contention resolution
• Pairwise-independent contention resolution
• Exact expressions for the maximal probability that all k-wise independent bits are 1
• Almost pairwise independence and resilience to deep learning attacks

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 Q3522268)