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

DOI10.1002/rsa.20423zbMath1281.68230OpenAlexW2077815142MaRDI QIDQ2856576

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

zbMATH Keywords

Fourier analysisdiscrete distributionsproperty testing\(k\)-wise independence

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost \(k\)-wise independence versus \(k\)-wise independence
• On the power of two-point based sampling
• Approximating probability distributions using small sample spaces
• Self-testing/correcting with applications to numerical problems
• On a set of almost deterministic k-independent random variables
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
• On construction of k-wise independent random variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Property testing and its connection to learning and approximation
• A complete problem for statistical zero knowledge
• Towards 3-query locally decodable codes of subexponential length
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• 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
• Simple Constructions of Almost k-wise Independent Random Variables
• Discrete (Legendre) orthogonal polynomials-a survey
• Efficient approximation of product distributions
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing juntas nearly optimally
• Constructing small sample spaces satisfying given constraints