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

DOI10.1002/RSA.20423MaRDI QIDQ2856576zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• \(H\)-wise independence
• Bounded independence versus symmetric tests
• Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract)
• The coin problem for product tests
• Almost \(k\)-wise independence versus \(k\)-wise independence
• Bounded independence vs. moduli
• \(H\)-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)