Simple Constructions of Almost k-wise Independent Random Variables

DOI10.1002/RSA.3240030308zbMATH Open0755.60002DBLPjournals/rsa/AlonGHP92OpenAlexW2163137752WikidataQ56959163 ScholiaQ56959163MaRDI QIDQ4014640FDOQ4014640

Authors: Noga Alon, Oded Goldreich, René Peralta, Johan Hastad 

Publication date: 18 October 1992

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240030308

Recommendations

• On construction of \(k\)-wise independent random variables
• On construction of \(k\)-wise independent random variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1496576

zbMATH Keywords

probabilistic computationremoving randomnessshiftregister sequences

Mathematics Subject Classification ID

Foundations of probability theory (60A99)

Cites Work

• Probabilistic algorithm for testing primality
• Equations over finite fields. An elementary approach

Cited In (only showing first 100 items - show all)

• New Results on Visual Cryptography
• On the computational power of depth-2 circuits with threshold and modulo gates
• Mining circuit lower bound proofs for meta-algorithms
• Random oracles and non-uniformity
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
• Pseudorandom generators for combinatorial checkerboards
• Pseudorandom generators for low sensitivity functions
• 3SUM, 3XOR, triangles
• Testing periodicity
• On the optimality of quantum encryption schemes
• Improved algorithms via approximations of probability distributions
• Binary Covering Arrays and Existentially Closed Graphs
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• On construction of \(k\)-wise independent random variables
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
• Packings with large minimum kissing numbers
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• A derandomization using min-wise independent permutations
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Hierarchy theorems for property testing
• A well-characterized approximation problem
• Hierarchy theorems for property testing
• Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete
• Derandomizing restricted isometries via the Legendre symbol
• The complexity of the matroid-greedoid partition problem
• Explicit constructions of RIP matrices and related problems
• The size-Ramsey number of trees
• Min-wise independent permutations
• On possible dependence structures of a set of random variables
• A note on monotone complexity and the rank of matrices
• On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
• The maximal probability that \(k\)-wise independent bits are all 1
• Binary quantum hashing
• Balancing output length and query bound in hardness preserving constructions of pseudorandom functions
• On rigid matrices and \(U\)-polynomials
• Locating and detecting arrays for interaction faults
• On the minimal Fourier degree of symmetric Boolean functions
• Approximating hyper-rectangles: Learning and pseudorandom sets
• Pseudorandom functions: three decades later
• Fast algorithms for approximately counting mismatches
• Extracting randomness: A survey and new constructions
• Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker
• Almost \(k\)-wise independence versus \(k\)-wise independence
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• The approximation of maximum subgraph problems
• Constructions of almost secure frameproof codes with applications to fingerprinting schemes
• Simple and efficient batch verification techniques for verifiable delay functions
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Extractors from Reed-Muller codes
• Pattern minimisation in cutting stock problems
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• Balanced hashing, color coding and approximate counting
• Almost \(k\)-wise independent sample spaces and their cryptologic applications
• Three XOR-lemmas -- an exposition
• The cell probe complexity of succinct data structures
• On the decisional complexity of problems over the reals
• Essential components in vector spaces over finite fields
• Counting solutions to polynomial systems via reductions
• Title not available (Why is that?)
• Matrix rigidity of random Toeplitz matrices
• Four decades of research on bent functions
• On designs in compact metric spaces and a universal bound on their size
• Secret-Sharing Schemes: A Survey
• Small-bias is not enough to hit read-once CNF
• The communication complexity of addition
• Parity check matrices and product representations of squares
• The isomorphism conjecture for constant depth reductions
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Improved parallel approximation of a class of integer programming problems
• Consensus patterns (probably) has no EPTAS
• An Almost m-wise Independent Random Permutation of the Cube
• Title not available (Why is that?)
• Almost \(k\)-wise independence and hard Boolean functions.
• On sparse parity check matrices (extended abstract)
• Extractors: low entropy requirements colliding with non-malleability
• Interactive Coding for Interactive Proofs
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• Worst-Case to Average-Case Reductions for Subclasses of P
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
• \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions
• Paradigms for Unconditional Pseudorandom Generators
• A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
• Quantum hashing for finite abelian groups
• \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
• On the joint entropy of \(d\)-wise-independent variables.
• Bit security as computational cost for winning games with high probability
• Polynomial data structure lower bounds in the group model
• Secure computation using leaky correlations (asymptotically optimal constructions)
• Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• Unified view for notions of bit security
• A connection between random variables and latin \(k\)-cubes
• Placing conditional disclosure of secrets in the communication complexity universe
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• One-tape Turing machine and branching program lower bounds for MCSP
• Fixing cracks in the concrete: random oracles with auxiliary input, revisited
• Title not available (Why is that?)

This page was built for publication: Simple Constructions of Almost k-wise Independent Random Variables

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