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)- 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
- On the minimal Fourier degree of symmetric Boolean functions
- Balancing output length and query bound in hardness preserving constructions of pseudorandom functions
- Locating and detecting arrays for interaction faults
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Fast algorithms for approximately counting mismatches
- Pseudorandom functions: three decades later
- On the relationship between -biased random variables and -dependent random variables
- Extracting randomness: A survey and new constructions
- Almost \(k\)-wise independence versus \(k\)-wise independence
- Capacity of interactive communication over erasure channels and channels with feedback
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Constructions of almost secure frameproof codes with applications to fingerprinting schemes
- Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker
- The approximation of maximum subgraph problems
- scientific article; zbMATH DE number 1959634 (Why is no real title available?)
- Short Proofs Are Hard to Find
- On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
- A one-time stegosystem and applications to efficient covert communication
- Simple and efficient batch verification techniques for verifiable delay functions
- Linear-size constant-query IOPs for delegating computation
- Extractors from Reed-Muller codes
- The function-inversion problem: barriers and opportunities
- Pattern minimisation in cutting stock problems
- Randomized OBDD-based graph algorithms
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Randomized OBDD-based graph algorithms
- Rigid matrices from rectangular PCPs
- Simple Direct Reduction of String (1,2)-OT to Rabin’s OT without Privacy Amplification
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Expanding Generating Sets for Solvable Permutation Groups
- Finding and counting small tournaments in large tournaments
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)
