Document Open Access Logo

Bounded Independence vs. Moduli

Authors Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2016.24.pdf
  • Filesize: 477 kB
  • 9 pages

Document Identifiers

Subject Classification

Keywords
  • Bounded independence
  • Modulus

Metrics

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

Abstract

Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer.  We show that Omega(n/m^2 log m) <= k <= 2n/m + 2.  For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m.  For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.

Cite As Get BibTex

Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded Independence vs. Moduli. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.24

Author Details

Ravi Boppana
Johan Håstad
Chin Ho Lee
Emanuele Viola

References

  1. Louay M. J. Bazzi. Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38(6):2220-2272, 2009. Google Scholar
  2. Mark Braverman. Polylogarithmic independence fools AC^0 circuits. J. of the ACM, 57(5), 2010. Google Scholar
  3. Neal Carothers. A short course on approximation theory. Available at http://personal.bgsu.edu/∼carother/Approx.html. Google Scholar
  4. Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Improved algorithms via approximations of probability distributions. J. Comput. System Sci., 61(1):81-107, 2000. URL: http://dx.doi.org/10.1006/jcss.1999.1695.
  5. E. Cheney. Introduction to approximation theory. McGraw-Hill, New York, New York, 1966. Google Scholar
  6. Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM J. on Computing, 39(8):3441-3462, 2010. Google Scholar
  7. Ilias Diakonikolas, Daniel Kane, and Jelani Nelson. Bounded independence fools degree-2 threshold functions. In 51th IEEE Symp. on Foundations of Computer Science (FOCS). IEEE, 2010. Google Scholar
  8. Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic. Efficient approximation of product distributions. Random Struct. Algorithms, 13(1):1-16, 1998. Google Scholar
  9. Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman. Fooling functions of halfspaces under product distributions. In 25th IEEE Conf. on Computational Complexity (CCC), pages 223-234. IEEE, 2010. Google Scholar
  10. Chin Ho Lee and Emanuele Viola. Some limitations of the sum of small-bias distributions. Available at http://www.ccs.neu.edu/home/viola/, 2015.
  11. Raghu Meka and David Zuckerman. Small-bias spaces for group products. In 13th Workshop on Randomization and Computation (RANDOM), volume 5687 of Lecture Notes in Computer Science, pages 658-672. Springer, 2009. Google Scholar
  12. Alexander A. Razborov. A simple proof of Bazzi’s theorem. ACM Transactions on Computation Theory (TOCT), 1(1), 2009. Google Scholar
  13. Avishay Tal. Tight bounds on The Fourier Spectrum of AC⁰. Electronic Colloquium on Computational Complexity, Technical Report TR14-174, 2014. Google Scholar
  14. L. Richard Turner. Inverse of the Vandermonde matrix with applications, 1966. NASA technical note D-3547 available at URL: http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19660023042.pdf.
  15. Emanuele Viola and Avi Wigderson. Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4:137-168, 2008. 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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact