Document Open Access Logo

Invariance Principle on the Slice

Authors Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.15.pdf
  • Filesize: 422 kB
  • 10 pages

Document Identifiers

Author Details

Yuval Filmus
Guy Kindler
Elchanan Mossel
Karl Wimmer

Cite As Get BibTex

Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance Principle on the Slice. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 15:1-15:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.15

Abstract

We prove a non-linear invariance principle for the slice. As applications, we prove versions of Majority is Stablest, Bourgain's tail theorem, and the Kindler-Safra theorem for the slice. From the latter we deduce a stability version of the t-intersecting Erdos-Ko-Rado theorem.

Subject Classification

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
    0
    Metadata Views

References

  1. Rudolf Ahlswede and Levon H. Khachatrian. The complete intersection theorem for systems of finite sets. Eur. J. Comb., 18(2):125-136, 1997. Google Scholar
  2. Rudolf Ahlswede and Levon H. Khachatrian. A pushing-pulling method: New proofs of intersection theorems. Combinatorica, 19(1):1-15, 1999. Google Scholar
  3. Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. In ITCS 2015, 2015. Google Scholar
  4. Charles F. Dunkl. A Krawtchouk polynomial addition theorem and wreath products of symmetric groups. Indiana Univ. Math. J., 25:335-358, 1976. Google Scholar
  5. 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
  6. Yuval Filmus. An orthogonal basis for functions over a slice of the boolean hypercube. Elec. J. Comb., 23(1):P1.23, 2016. Google Scholar
  7. Ehud Friedgut. On the measure of intersecting families, uniqueness and stability. Combinatorica, 28(5):503-528, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2318-9.
  8. Subhash Khot. Inapproximability of NP-complete problems, discrete fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010. Google Scholar
  9. Guy Kindler, Naomi Kirshner, and Ryan O'Donnell. Gaussian noise sensitivity and Fourier tails, 2014. Manuscript. Google Scholar
  10. Elchanan Mossel and Yuval Filmus. Harmonicity and invariance on slices of the Boolean cube. In 31st Conf. Comp. Comp., 2016. Google Scholar
  11. 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
  12. Richard M. Wilson. The exact bound in the Erdős-Ko-Rado theorem. Combinatorica, 4:247-257, 1984. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact