Simple Constructions of Almost k-wise Independent Random Variables
From MaRDI portal
Publication:4014640
DOI10.1002/RSA.3240030308zbMath0755.60002DBLPjournals/rsa/AlonGHP92OpenAlexW2163137752WikidataQ56959163 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
Related Items (only showing first 100 items - show all)
Binary Covering Arrays and Existentially Closed Graphs ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ On sparse parity check matrices (extended abstract) ⋮ Extractors: low entropy requirements colliding with non-malleability ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Efficient Linear and Affine Codes for Correcting Insertions/Deletions ⋮ Bit security as computational cost for winning games with high probability ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Rigid matrices from rectangular PCPs ⋮ Optimal explicit small-depth formulas for the coin problem ⋮ Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker ⋮ The size-Ramsey number of trees ⋮ Optimal $\varepsilon$-Biased Sets with Just a Little Randomness ⋮ Simple Direct Reduction of String (1,2)-OT to Rabin’s OT without Privacy Amplification ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 ⋮ Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited ⋮ Quantum hashing for finite abelian groups ⋮ On the optimality of quantum encryption schemes ⋮ A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Randomized OBDD-based graph algorithms ⋮ MODp-tests, almost independence and small probability spaces ⋮ Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Secure computation using leaky correlations (asymptotically optimal constructions) ⋮ The cell probe complexity of succinct data structures ⋮ New Results on Visual Cryptography ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ Expanding Generating Sets for Solvable Permutation Groups ⋮ Randomized OBDD-Based Graph Algorithms ⋮ Binary quantum hashing ⋮ Random oracles and non-uniformity ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ A connection between random variables and latin \(k\)-cubes ⋮ Matrix rigidity of random Toeplitz matrices ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality ⋮ Packings with large minimum kissing numbers ⋮ A derandomization using min-wise independent permutations ⋮ The function-inversion problem: barriers and opportunities ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions ⋮ Improved boolean formulas for the Ramsey graphs ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields] ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ 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] ⋮ On the minimal Fourier degree of symmetric Boolean functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The isomorphism conjecture for constant depth reductions ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Locating and detecting arrays for interaction faults ⋮ On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries ⋮ Unnamed Item ⋮ On rigid matrices and \(U\)-polynomials ⋮ Unnamed Item ⋮ Hierarchy theorems for property testing ⋮ Explicit constructions of RIP matrices and related problems ⋮ Four decades of research on bent functions ⋮ Simple and efficient batch verification techniques for verifiable delay functions ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ A one-time stegosystem and applications to efficient covert communication ⋮ On possible dependence structures of a set of random variables ⋮ Amplification and Derandomization without Slowdown ⋮ Pattern minimisation in cutting stock problems ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ The approximation of maximum subgraph problems ⋮ Hierarchy Theorems for Property Testing ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Secret-Sharing Schemes: A Survey ⋮ \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ Constructions of almost secure frameproof codes with applications to fingerprinting schemes ⋮ Bounded Independence Plus Noise Fools Products ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Parity check matrices and product representations of squares ⋮ Small-bias is not enough to hit read-once CNF ⋮ The communication complexity of addition ⋮ A well-characterized approximation problem ⋮ Testing periodicity ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Unnamed Item ⋮ Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets ⋮ Extractors from Reed-Muller codes ⋮ [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma] ⋮ Unnamed Item ⋮ Interactive Coding for Interactive Proofs ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ The complexity of the matroid-greedoid partition problem ⋮ Essential components in vector spaces over finite fields ⋮ A note on monotone complexity and the rank of matrices ⋮ Quantum Property Testing for Bounded-Degree Graphs
Cites Work
This page was built for publication: Simple Constructions of Almost k-wise Independent Random Variables
