Almost \(k\)-wise independence versus \(k\)-wise independence

DOI10.1016/S0020-0190(03)00359-4zbMath1178.68251OpenAlexW1994423049MaRDI QIDQ1028993

Yishay Mansour, Oded Goldreich, Noga Alon

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00359-4

zbMATH Keywords

combinatorial problemstheory of computation\(k\)-wise independent distributionsalmost \(k\)-wise independent distributionssmall probability spacessmall-bias probability spaces

Mathematics Subject Classification ID

Related Items (12)

Randomized OBDD-based graph algorithms ⋮ On-board vehicle data stream monitoring using mine-fleet and fast resource constrained monitoring of correlation matrices ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Deterministic Massively Parallel Connectivity ⋮ Unnamed Item ⋮ Revisiting iterated attacks in the context of decorrelation theory ⋮ Bounded Independence Plus Noise Fools Products ⋮ Unnamed Item ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Oblivious network RAM and leveraging parallelism to achieve obliviousness ⋮ Explicit two-source extractors and resilient functions ⋮ Robust characterizations of k -wise independence over product spaces and related testing results

Cites Work

• Unnamed Item
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Simple Constructions of Almost k-wise Independent Random Variables

This page was built for publication: Almost \(k\)-wise independence versus \(k\)-wise independence