Robust characterizations of k-wise independence over product spaces and related testing results

DOI10.1002/RSA.20423zbMATH Open1281.68230OpenAlexW2077815142MaRDI QIDQ2856576FDOQ2856576

Authors: Ronitt Rubinfeld, Ning Xie 

Publication date: 29 October 2013

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20423

Recommendations

• Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract)
• scientific article; zbMATH DE number 7378666
• Bounded independence versus symmetric tests
• Almost \(k\)-wise independence versus \(k\)-wise independence
• \(H\)-wise independence

zbMATH Keywords

discrete distributionsFourier analysisproperty testing\(k\)-wise independence

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Cites Work

• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Property testing and its connection to learning and approximation
• Simple Constructions of Almost k-wise Independent Random Variables
• Self-testing/correcting with applications to numerical problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Discrete (Legendre) orthogonal polynomials-a survey
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• On a set of almost deterministic k-independent random variables
• On the power of two-point based sampling
• A complete problem for statistical zero knowledge
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
• Towards 3-query locally decodable codes of subexponential length
• Efficient approximation of product distributions
• Testing juntas nearly optimally
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Almost \(k\)-wise independence versus \(k\)-wise independence
• On construction of \(k\)-wise independent random variables
• Constructing small sample spaces satisfying given constraints
• Title not available (Why is that?)
• Approximating probability distributions using small sample spaces

Cited In (2)

• Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract)
• Almost \(k\)-wise independence versus \(k\)-wise independence

This page was built for publication: Robust characterizations of \(k\)-wise independence over product spaces and related testing results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2856576)