On Closeness to k-Wise Uniformity

Authors Ryan O'Donnell, Yu Zhao



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.54.pdf
  • Filesize: 0.5 MB
  • 19 pages

Document Identifiers

Author Details

Ryan O'Donnell
  • Carnegie Mellon University, Pittsburgh, PA, USA
Yu Zhao
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet BibTex

Ryan O'Donnell and Yu Zhao. On Closeness to k-Wise Uniformity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.54

Abstract

A probability distribution over {-1, 1}^n is (epsilon, k)-wise uniform if, roughly, it is epsilon-close to the uniform distribution when restricted to any k coordinates. We consider the problem of how far an (epsilon, k)-wise uniform distribution can be from any globally k-wise uniform distribution. We show that every (epsilon, k)-wise uniform distribution is O(n^{k/2}epsilon)-close to a k-wise uniform distribution in total variation distance. In addition, we show that this bound is optimal for all even k: we find an (epsilon, k)-wise uniform distribution that is Omega(n^{k/2}epsilon)-far from any k-wise uniform distribution in total variation distance. For k=1, we get a better upper bound of O(epsilon), which is also optimal. One application of our closeness result is to the sample complexity of testing whether a distribution is k-wise uniform or delta-far from k-wise uniform. We give an upper bound of O(n^{k}/delta^2) (or O(log n/delta^2) when k = 1) on the required samples. We show an improved upper bound of O~(n^{k/2}/delta^2) for the special case of testing fully uniform vs. delta-far from k-wise uniform. Finally, we complement this with a matching lower bound of Omega(n/delta^2) when k = 2. Our results improve upon the best known bounds from [Alon et al., 2007], and have simpler proofs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • k-wise independence
  • property testing
  • Fourier analysis
  • Boolean function

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems, pages 3591-3599, 2015. Google Scholar
  2. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 689-708, 2015. Google Scholar
  3. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 496-505, 2007. Google Scholar
  4. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986. Google Scholar
  5. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures &Algorithms, 3(3):289-304, 1992. Google Scholar
  6. Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107-110, 2003. URL: http://dx.doi.org/10.1016/S0020-0190(03)00359-4.
  7. Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Computational Complexity, 18(2):249-271, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0272-6.
  8. Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages 442-451, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959920.
  9. Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 259-269, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892113.
  10. Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 381-390, 2004. URL: http://dx.doi.org/10.1145/1007352.1007414.
  11. Louay M. J. Bazzi. Polylogarithmic independence can fool DNF formulas. SIAM Journal on Computing, 38(6):2220-2272, 2009. URL: http://dx.doi.org/10.1137/070691954.
  12. Mark Braverman. Polylogarithmic independence fools AC^0 circuits. Journal of the ACM, 57(5):28:1-28:10, 2010. URL: http://dx.doi.org/10.1145/1754399.1754401.
  13. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 670-683, 2016. URL: http://dx.doi.org/10.1145/2897518.2897528.
  14. Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, and Roman Smolensky. The bit extraction problem of t-resilient functions. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 396-407, 1985. URL: http://dx.doi.org/10.1109/SFCS.1985.55.
  15. Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 685-694. IEEE, 2016. Google Scholar
  16. Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68-75. Springer, 2011. Google Scholar
  17. Richard M. Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4):762-773, 1985. URL: http://dx.doi.org/10.1145/4221.4226.
  18. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 132-145, 2017. URL: http://dx.doi.org/10.1145/3055399.3055485.
  19. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 168-177. IEEE, 2016. Google Scholar
  20. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1053, 1986. URL: http://dx.doi.org/10.1137/0215074.
  21. Florence Jessie MacWilliams and Neil James Alexander Sloane. The theory of error-correcting codes. Elsevier, 1977. Google Scholar
  22. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. URL: http://dx.doi.org/10.1137/0222053.
  23. Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014. Google Scholar
  24. Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750-4755, 2008. URL: http://dx.doi.org/10.1109/TIT.2008.928987.
  25. Calyampudi Radhakrishna Rao. Factorial experiments derivable from combinatorial arrangements of arrays. Journal of the Royal Statistical Society, 9(1):128-139, 1947. Google Scholar
  26. Ronitt Rubinfeld and Rocco A. Servedio. Testing monotone high-dimensional distributions. Random Structures &Algorithms, 34(1):24-44, 2009. URL: http://dx.doi.org/10.1002/rsa.20247.
  27. Ronitt Rubinfeld and Ning Xie. Robust characterizations of k-wise independence over product spaces and related testing results. Random Structures &Algorithms, 43(3):265-312, 2013. Google Scholar
  28. Ning Xie. Testing k-wise independent distributions. PhD thesis, Massachusetts Institute of Technology, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail