Document Open Access Logo

Noise Stability Is Computable and Approximately Low-Dimensional

Authors Anindya De, Elchanan Mossel, Joe Neeman

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.10.pdf
  • Filesize: 0.54 MB
  • 11 pages

Document Identifiers

Author Details

Anindya De
Elchanan Mossel
Joe Neeman

Cite As Get BibTex

Anindya De, Elchanan Mossel, and Joe Neeman. Noise Stability Is Computable and Approximately Low-Dimensional. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.10

Abstract

Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of R^n for n >= 1 to k parts with given Gaussian measures mu_1, ..., mu_k. We call a partition epsilon-optimal, if its noise stability is optimal up to an additive epsilon. In this paper, we give an explicit, computable function n(epsilon) such that an epsilon-optimal partition exists in R^{n(epsilon)}. This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent work.

Subject Classification

Keywords
  • Gaussian noise stability; Plurality is stablest; Ornstein Uhlenbeck operator

Metrics

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

References

  1. S. G. Bobkov. Isoperimetric problem for uniform enlargement. Studia Math, 123(1):81-95, 1997. Google Scholar
  2. C. Borell. The Brunn-Minkowski inequality in Gauss space. Invent. Math., 30:207-216, 1975. Google Scholar
  3. C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1-13, 1985. Google Scholar
  4. J. Corneli, I. Corwin, S. Hurder, V. Sesum, Y. Xu, E. Adams, D. Davis, M. Lee, R. Visocchi, N. Hoffman, and Robert M. Hardt. Double bubbles in gauss space and spheres. Houston Journal of Mathematics, 34(1):181-204, 2008. Google Scholar
  5. A. De and R. Servedio. Efficient deterministic approximate counting for low-degree polynomial threshold functions. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, pages 832-841, 2014. Full version at http://arxiv.org/abs/1311.7178. Google Scholar
  6. B. Ghazi, P. Kamath, and M. Sudan. Decidability of non-interactive simulation of joint distributions. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 545-554, 2016. Google Scholar
  7. S. Heilman, E. Mossel, and J. Neeman. Standard simplices and pluralities are not the most noise stable. Israel Journal of Mathematics, pages 1-21, 2014. Google Scholar
  8. Steven Heilman. Euclidean partitions optimizing noise stability. Electron. J. Probab, 19(71):1-37, 2014. Google Scholar
  9. M. Hutchings, F. Morgan, M. Ritoré, and A. Ros. Proof of the double bubble conjecture. Res. Announc. Amer. Math. Soc, 6:45-49, 2000. Google Scholar
  10. M. Hutchings, F. Morgan, M. Ritoré, and A. Ros. Proof of the double bubble conjecture. Ann. of Math., 155:459-489, 2002. Google Scholar
  11. G. Kalai. A Fourier-theoretic perspective on the Concordet paradox and Arrow’s theorem. Adv. in Appl. Math., 29(3):412-426, 2002. Google Scholar
  12. S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for Max-Cut and other 2-variable CSPs? In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pages 146-154, 2004. Google Scholar
  13. S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput., 37:319-357, 2007. URL: http://www.stat.berkeley.edu/~mossel/publications/max_cut_final.pdf.
  14. P. Kothari, A. Nayyeri, R. O'Donnell, and C. Wu. Testing surface area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1204-1214, 2014. Google Scholar
  15. M. Ledoux. Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bull. Sci. Math., 118:485-510, 1994. Google Scholar
  16. E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Ann. Math., 171(1):295-341, 2010. Google Scholar
  17. J. Neeman. Testing surface area with arbitrary accuracy. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 393-397, 2014. Google Scholar
  18. Prasad Raghavendra and David Steurer. How to round any csp. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 586-594. IEEE, 2009. Google Scholar
  19. Ben W. Reichardt, Cory Heilmann, Yuan Y. Lai, and Anita Spielman. Proof of the double bubble conjecture in r4 and certain higher dimensional cases. Pacific Journal of Mathematics, 208(2):347-366, 2003. Google Scholar
  20. V. Sudakov and B. Tsirel’son. Extremal properties of half-spaces for spherically invariant measures. J. Soviet Math., 9:9-18, 1978. Translated from Zap. Nauchn. Sem. Leningrad. Otdel. Math. Inst. Steklova. 41 (1974), 14-21. 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