Simple Constructions of Almost k-wise Independent Random Variables
From MaRDI portal
Publication:4014640
DOI10.1002/rsa.3240030308zbMath0755.60002OpenAlexW2163137752WikidataQ56959163 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
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, 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, Three XOR-Lemmas — An Exposition, Unnamed Item, An Almost m-wise Independent Random Permutation of the Cube, On the computational power of depth-2 circuits with threshold and modulo gates, Capacity of Interactive Communication over Erasure Channels and Channels with Feedback, Short Proofs Are Hard to Find, Near-optimal pseudorandom generators for constant-depth read-once formulas, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Almost \(k\)-wise independence versus \(k\)-wise independence, Approximating hyper-rectangles: Learning and pseudorandom sets, Unnamed Item, Balanced Hashing, Color Coding and Approximate Counting, Min-wise independent permutations, Improved algorithms via approximations of probability distributions, On designs in compact metric spaces and a universal bound on their size, Robust characterizations of k -wise independence over product spaces and related testing results, Extracting randomness: A survey and new constructions, On the decisional complexity of problems over the reals, Fast algorithms for approximately counting mismatches, Pseudorandom Functions: Three Decades Later, Mining circuit lower bound proofs for meta-algorithms, 3SUM, 3XOR, triangles
Cites Work
