Simple Constructions of Almost k-wise Independent Random Variables
From MaRDI portal
Publication:4014640
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)- Balanced hashing, color coding and approximate counting
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- Three XOR-lemmas -- an exposition
- Almost \(k\)-wise independent sample spaces and their cryptologic applications
- Bounded independence plus noise fools products
- Optimal explicit small-depth formulas for the coin problem
- Small bias requires large formulas
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Improved boolean formulas for the Ramsey graphs
- scientific article; zbMATH DE number 7650109 (Why is no real title available?)
- Amplification and Derandomization without Slowdown
- Sample spaces with small bias on neighborhoods and error-correcting communication protocols
- 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
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Robust characterizations of \(k\)-wise independence over product spaces and related testing results
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
- Counting solutions to polynomial systems via reductions
- 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
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- scientific article; zbMATH DE number 176875 (Why is no real title available?)
- Secret-Sharing Schemes: A Survey
- Small-bias is not enough to hit read-once CNF
- The communication complexity of addition
- Quantum property testing for bounded-degree graphs
- Parity check matrices and product representations of squares
- The isomorphism conjecture for constant depth reductions
- Explicit Near-Ramanujan Graphs of Every Degree
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Deterministic document exchange protocols and almost optimal binary codes for edit errors
- Nearly optimal pseudorandomness from hardness
- Improved parallel approximation of a class of integer programming problems
- Optimal \(\varepsilon\)-biased sets with just a little randomness
- New Results on Visual Cryptography
- On the computational power of depth-2 circuits with threshold and modulo gates
- Component stability in low-space massively parallel computation
- Consensus patterns (probably) has no EPTAS
- 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
- Mining circuit lower bound proofs for meta-algorithms
- 3SUM, 3XOR, triangles
- Testing periodicity
- Pseudorandom generators for low sensitivity functions
- On the optimality of quantum encryption schemes
- An Almost m-wise Independent Random Permutation of the Cube
- Almost \(k\)-wise independence and hard Boolean functions.
- Improved algorithms via approximations of probability distributions
- Interactive Coding for Interactive Proofs
- Binary Covering Arrays and Existentially Closed Graphs
- On sparse parity check matrices (extended abstract)
- Universal Hashing via Integer Arithmetic Without Primes, Revisited
- Extractors: low entropy requirements colliding with non-malleability
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Worst-Case to Average-Case Reductions for Subclasses of P
- On construction of \(k\)-wise independent random variables
- 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)
- \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Efficient Linear and Affine Codes for Correcting Insertions/Deletions
- Packings with large minimum kissing numbers
- Quantum hashing for finite abelian groups
- Paradigms for Unconditional Pseudorandom Generators
- Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
- \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
- Secure computation using leaky correlations (asymptotically optimal constructions)
- Polynomial data structure lower bounds in the group model
- A derandomization using min-wise independent permutations
- Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
- Hierarchy theorems for property testing
- A well-characterized approximation problem
- On deterministic sketching and streaming for sparse recovery and norm estimation
- Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete
- Derandomizing restricted isometries via the Legendre symbol
- Hierarchy theorems for property testing
- The complexity of the matroid-greedoid partition problem
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- A connection between random variables and latin \(k\)-cubes
- Explicit constructions of RIP matrices and related problems
- Unified view for notions of bit security
- On possible dependence structures of a set of random variables
- Min-wise independent permutations
- The size-Ramsey number of trees
- A note on monotone complexity and the rank of matrices
- Placing conditional disclosure of secrets in the communication complexity universe
- On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- One-tape Turing machine and branching program lower bounds for MCSP
- The maximal probability that \(k\)-wise independent bits are all 1
- Deterministic approximation of random walks in small space
- Binary quantum hashing
- On rigid matrices and \(U\)-polynomials
- Fixing cracks in the concrete: random oracles with auxiliary input, revisited
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)
