Simple Constructions of Almost k-wise Independent Random Variables
From MaRDI portal
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
Cites work
Cited in
(only showing first 100 items - show all)- 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
- On the relationship between -biased random variables and -dependent random variables
- On construction of \(k\)-wise independent random variables
- 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
- Randomized OBDD-based graph algorithms
- Secure computation using leaky correlations (asymptotically optimal constructions)
- Random oracles and non-uniformity
- Matrix rigidity of random Toeplitz matrices
- Constructions of almost secure frameproof codes with applications to fingerprinting schemes
- On the decisional complexity of problems over the reals
- A connection between random variables and latin \(k\)-cubes
- Pattern minimisation in cutting stock problems
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
- Placing conditional disclosure of secrets in the communication complexity universe
- Essential components in vector spaces over finite fields
- The function-inversion problem: barriers and opportunities
- Linear-size constant-query IOPs for delegating computation
- Mining circuit lower bound proofs for meta-algorithms
- Quantum hashing for finite abelian groups
- The cell probe complexity of succinct data structures
- Locating and detecting arrays for interaction faults
- On deterministic sketching and streaming for sparse recovery and norm estimation
- A one-time stegosystem and applications to efficient covert communication
- Extractors from Reed-Muller codes
- 3SUM, 3XOR, triangles
- Simple and efficient batch verification techniques for verifiable delay functions
- Interactive Coding for Interactive Proofs
- On construction of \(k\)-wise independent random variables
- Robust characterizations of k-wise independence over product spaces and related testing results
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Balancing output length and query bound in hardness preserving constructions of pseudorandom functions
- Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete
- On the joint entropy of d-wise-independent variables.
- Derandomizing restricted isometries via the Legendre symbol
- Secret-Sharing Schemes: A Survey
- Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
- Quantum property testing for bounded-degree graphs
- Three XOR-lemmas -- an exposition
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Expanding Generating Sets for Solvable Permutation Groups
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Binary quantum hashing
- On the optimality of quantum encryption schemes
- New Results on Visual Cryptography
- Consensus patterns (probably) has no EPTAS
- Randomized OBDD-based graph algorithms
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Balanced hashing, color coding and approximate counting
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
- Pseudorandom generators for combinatorial checkerboards
- On the minimal Fourier degree of symmetric Boolean functions
- scientific article; zbMATH DE number 176875 (Why is no real title available?)
- On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
- Hierarchy theorems for property testing
- scientific article; zbMATH DE number 1959634 (Why is no real title available?)
- scientific article; zbMATH DE number 1496576 (Why is no real title available?)
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- On possible dependence structures of a set of random variables
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- The approximation of maximum subgraph problems
- Bounded independence plus noise fools products
- Efficient approximation of product distributions
- An Almost m-wise Independent Random Permutation of the Cube
- Improved boolean formulas for the Ramsey graphs
- Hierarchy theorems for property testing
- Capacity of interactive communication over erasure channels and channels with feedback
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Pseudorandom generators for low sensitivity functions
- Small bias requires large formulas
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- Pseudorandom functions: three decades later
- \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
- Polynomial data structure lower bounds in the group model
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- Short Proofs Are Hard to Find
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Worst-Case to Average-Case Reductions for Subclasses of P
- On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- Amplification and Derandomization without Slowdown
- Deterministic approximation of random walks in small space
- The maximal probability that k-wise independent bits are all 1
- Small-bias is not enough to hit read-once CNF
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)
