Harmonicity and Invariance on Slices of the Boolean Cube

Authors Yuval Filmus, Elchanan Mossel



PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.16.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Yuval Filmus
Elchanan Mossel

Cite AsGet BibTex

Yuval Filmus and Elchanan Mossel. Harmonicity and Invariance on Slices of the Boolean Cube. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CCC.2016.16

Abstract

In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree functions. Here we provide an alternative proof for general low-degree functions, with no constraints on the influences. We show that any real-valued function on the slice, whose degree when written as a harmonic multi-linear polynomial is o(sqrt(n)), has approximately the same distribution under the slice and cube measure. Our proof is based on a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, ours decomposition is applied in a non-reversible non-stationary setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that 1) one cannot distinguish between the slice and the cube based on functions of little of of n coordinates and 2) Boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(sqrt(n)).
Keywords
  • analysis of boolean functions
  • invariance principle
  • Johnson association scheme
  • the slice

Metrics

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

References

  1. Franćois Bergeron. Algebraic Combinatorics and Coinvariant Spaces. CMS Treatises in Mathematics. A K Peters, 2009. Google Scholar
  2. Ravi B Boppana. The average sensitivity of bounded-depth circuits. Information Processing Letters, 63(5):257-261, 1997. Google Scholar
  3. Charles F. Dunkl. A Krawtchouk polynomial addition theorem and wreath products of symmetric groups. Indiana Univ. Math. J., 25:335-358, 1976. Google Scholar
  4. Charles F. Dunkl. Orthogonal functions on some permutation groups. In Relations between combinatorics and other parts of mathematics, volume 34 of Proc. Symp. Pure Math., pages 129-147, Providence, RI, 1979. Amer. Math. Soc. Google Scholar
  5. Yuval Filmus. An orthogonal basis for functions over a slice of the boolean hypercube. Elec. J. Comb., 23(1):P1.23, 2016. Google Scholar
  6. Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance principle on the slice. In 31st Conf. Comp. Comp., 2016. Google Scholar
  7. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Silvio Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 143-170. JAI Press, 1989. Google Scholar
  8. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963. Google Scholar
  9. Guy Kindler. Property testing, PCP and Juntas. PhD thesis, Tel-Aviv University, 2002. Google Scholar
  10. Guy Kindler and Shmuel Safra. Noise-resistant Boolean functions are juntas, 2004. Unpublished manuscript. Google Scholar
  11. Tzong-Yau Lee and Horng-Tzer Yau. Logarithmic Sobolev inequality for some models of random walks. Ann. Prob., 26(4):1855-1873, 1998. Google Scholar
  12. N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, fourier transform and learnability. Journal of the ACM, 40(3):607-620, 1993. Google Scholar
  13. Terry J. Lyons and T. S. Zhang. Decomposition of Dirichlet processes and its application. Ann. Probab., 22(1):494-524, 1994. Google Scholar
  14. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Ann. Math., 171:295-341, 2010. Google Scholar
  15. Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math J., 134(1):165-197, 2006. Google Scholar
  16. Ryan O'Donnell and Karl Wimmer. Approximation by DNF: Examples and counterexamples. In Automata, Languages and Programming, volume 4596 of Lecture Notes in Computer Science, pages 195-206. Springer Berlin Heidelberg, 2007. Google Scholar
  17. Murali K. Srinivasan. Symmetric chains, Gelfand-Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme. J. Algebr. Comb., 34(2):301-322, 2011. Google Scholar
  18. Avishay Tal. Tight bounds on the Fourier spectrum of AC⁰. Manuscript, 2014. 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