Simple Constructions of Almost k-wise Independent Random Variables
From MaRDI portal
Publication:4014640
DOI10.1002/rsa.3240030308zbMath0755.60002WikidataQ56959163 ScholiaQ56959163MaRDI QIDQ4014640
Oded Goldreich, Noga Alon, René Peralta, Johan T. Håstad
Publication date: 18 October 1992
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240030308
60A99: Foundations of probability theory
Related Items
Unnamed Item, An Almost m-wise Independent Random Permutation of the Cube, Improved boolean formulas for the Ramsey graphs, Hierarchy Theorems for Property Testing, Binary Covering Arrays and Existentially Closed Graphs, Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker, Simple Direct Reduction of String (1,2)-OT to Rabin’s OT without Privacy Amplification, The size-Ramsey number of trees, \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials, Improved parallel approximation of a class of integer programming problems, A well-characterized approximation problem, A derandomization using min-wise independent permutations, Parity check matrices and product representations of squares, The complexity of the matroid-greedoid partition problem, A note on monotone complexity and the rank of matrices, Almost \(k\)-wise independence versus \(k\)-wise independence, On the computational power of depth-2 circuits with threshold and modulo gates, Approximating hyper-rectangles: Learning and pseudorandom sets, Extracting randomness: A survey and new constructions, Fast algorithms for approximately counting mismatches, Packings with large minimum kissing numbers, Almost \(k\)-wise independence and hard Boolean functions., Min-wise independent permutations, Improved algorithms via approximations of probability distributions, On designs in compact metric spaces and a universal bound on their size, On the decisional complexity of problems over the reals, A connection between random variables and latin \(k\)-cubes, Pattern minimisation in cutting stock problems, The cell probe complexity of succinct data structures, Locating and detecting arrays for interaction faults, Extractors from Reed-Muller codes, On the optimality of quantum encryption schemes, Small Sample Spaces Cannot Fool Low Degree Polynomials, Balanced Hashing, Color Coding and Approximate Counting
Cites Work
