Document Open Access Logo

Convex Influences

Authors Anindya De, Shivam Nadimpalli, Rocco A. Servedio

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.53.pdf
  • Filesize: 0.78 MB
  • 21 pages

Document Identifiers

Author Details

Anindya De
  • University of Pennsylvania, Philadelphia, PA, USA
Shivam Nadimpalli
  • Columbia University, New York, NY, USA
Rocco A. Servedio
  • Columbia University, New York, NY, USA

Funding

This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation (NSF).
  • De, Anindya: A.D. is supported by NSF grants CCF-1910534, CCF-1926872, and CCF-2048128.
  • Nadimpalli, Shivam: S.N. is supported by NSF grants CCF-1563155 and by CCF-1763970.
  • Servedio, Rocco A.: R.A.S. is supported by NSF grants CCF-1814873, IIS-1838154, CCF-1563155, and by the Simons Collaboration on Algorithms and Geometry.

Acknowledgements

This work was done while A. D. was participating in the "Probability, Geometry, and Computation in High Dimensions" program at the Simons Institute for the Theory of Computing. A. D. wishes to thank the Simons Institute for their support.

Cite AsGet BibTex

Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex Influences. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.53

Abstract

We introduce a new notion of influence for symmetric convex sets over Gaussian space, which we term "convex influence". We show that this new notion of influence shares many of the familiar properties of influences of variables for monotone Boolean functions f: {±1}ⁿ → {±1}. Our main results for convex influences give Gaussian space analogues of many important results on influences for monotone Boolean functions. These include (robust) characterizations of extremal functions, the Poincaré inequality, the Kahn-Kalai-Linial theorem [J. Kahn et al., 1988], a sharp threshold theorem of Kalai [G. Kalai, 2004], a stability version of the Kruskal-Katona theorem due to O'Donnell and Wimmer [R. O'Donnell and K. Wimmer, 2009], and some partial results towards a Gaussian space analogue of Friedgut’s junta theorem [E. Friedgut, 1998]. The proofs of our results for convex influences use very different techniques than the analogous proofs for Boolean influences over {±1}ⁿ. Taken as a whole, our results extend the emerging analogy between symmetric convex sets in Gaussian space and monotone Boolean functions from {±1}ⁿ to {±1}.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Mathematics of computing → Probability and statistics
Keywords
  • Fourier analysis of Boolean functions
  • convex geometry
  • influences
  • threshold phenomena

Metrics

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

Related Versions

References

  1. M. Y. An. Log-concave probability distributions: Theory and statistical testing. Technical Report Economics Working Paper Archive at WUSTL, Washington University at St. Louis, 1995. Google Scholar
  2. S. Artstein-Avidan, A. Giannopoulos, and V.D. Milman. Asymptotic Geometric Analysis, Part I, volume 202 of Mathematical Surveys and Monographs. American Mathematical Society, 2015. Google Scholar
  3. W. Beckner. Inequalities in Fourier analysis. Annals of Mathematics, 102:159-182, 1975. Google Scholar
  4. M. Ben-Or and N. Linial. Collective coin flipping. In Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 408-416, 1985. Google Scholar
  5. Andrew C. Berry. The Accuracy of the Gaussian Approximation to the Sum of Independent Variates. Transactions of the American Mathematical Society, 49(1):122-136, 1941. Google Scholar
  6. A. Blum, C. Burch, and J. Langford. On learning monotone boolean functions. In Proceedings of the Thirty-Ninth Annual Symposium on Foundations of Computer Science, pages 408-415, 1998. Google Scholar
  7. A. Bonami. Etude des coefficients Fourier des fonctiones de L^p(G). Ann. Inst. Fourier (Grenoble), 20(2):335-402, 1970. Google Scholar
  8. C. Borell. The Brunn-Minkowski inequality in Gauss space. Invent. Math., 30:207-216, 1975. Google Scholar
  9. C. Borell. The Ehrhard inequality. C. R. Math. Acad. Sci. Paris, 337:663-666, 2003. Google Scholar
  10. C. Borell. Inequalities of the Brunn-Minkoski type for Gaussian measures. Probab. Theory Related Fields, 140:195-205, 2008. Google Scholar
  11. Nader Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions. Journal of the ACM, 43(4):747-770, 1996. Google Scholar
  12. Xi Chen, Adam Freilich, Rocco A Servedio, and Timothy Sun. Sample-Based High-Dimensional Convexity Testing. In APPROX/RANDOM 2017, 2017. Google Scholar
  13. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 523-536, 2017. Google Scholar
  14. A. De, S. Nadimpalli, and R. A. Servedio. Quantitative Correlation Iequalities via Semigroup Interpolation. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021. Google Scholar
  15. Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex influences. arXiv preprint, 2021. URL: http://arxiv.org/abs/2109.03107.
  16. Anindya De and Rocco A. Servedio. Weak learning convex sets under normal distributions. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 1399-1428. PMLR, 2021. Google Scholar
  17. A. Dinghas. Über eine Klasse superadditiver Mengenfunktionale von Brunn Minkowski Lusternik-schem Typus. Math.Zeitschr., 68:111-125, 1957. Google Scholar
  18. Rick Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 5 edition, 2019. URL: https://doi.org/10.1017/9781108591034.
  19. A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123-160. Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961. Google Scholar
  20. A. Ehrhard. Symétrisation dans l'espace de gauss. Math Scand., 53:281-301, 1983. Google Scholar
  21. Ronen Eldan and Renan Gross. Concentration on the Boolean hypercube via pathwise stochastic analysis. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 208-221. ACM, 2020. Google Scholar
  22. Carl-Gustav Esseen. On the Liapunoff limit of error in the theory of probability. Arkiv för matematik, astronomi och fysik, A:1-19, 1942. Google Scholar
  23. Alessio Figalli. Personal communication, 2020. Google Scholar
  24. E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):474-483, 1998. Google Scholar
  25. E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124:2993-3002, 1996. Google Scholar
  26. T.E. Harris. A lower bound for the critical probability in a certain percolation process. Proc. Camb. Phil. Soc., 56:13-20, 1960. Google Scholar
  27. I.A. Ibragimov. On the composition of unimodal distributions. Theory Prob. Appl., 1, 1956. Google Scholar
  28. J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS), pages 68-80, 1988. Google Scholar
  29. G. Kalai. Social indeterminacy. Econometrica, 72(5):1565-1581, 2004. Google Scholar
  30. Gil Kalai and Shmuel Safra. Threshold Phenomena and Influence with Some Perspectives from Mathematics, Computer Science, and Economics. In Computational Complexity and Statistical Physics, pages 25-60. Oxford University Press, 2005. Google Scholar
  31. G. Katona. A theorem of finite sets. Journal of Graph Theory - JGT, pages 381-401, June 2010. URL: https://doi.org/10.1007/978-0-8176-4842-8_27.
  32. Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPIcs, pages 26:1-26:17, 2021. Google Scholar
  33. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pages 52-58, 2015. Google Scholar
  34. Daniel J Kleitman. Families of non-disjoint subsets. Journal of Combinatorial Theory, 1(1):153-155, 1966. Google Scholar
  35. A. Klivans, R. O'Donnell, and R. Servedio. Learning geometric concepts via Gaussian surface area. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 541-550, 2008. Google Scholar
  36. J. Kruskal. The number of simplices in a complex. In R. Bellman, editor, Mathematical Optimization Techniques, pages 251-278. University of California, Press, Berkeley, 1963. Google Scholar
  37. Rafał Latała and Krzysztof Oleszkiewicz. Gaussian measures of dilatations of convex symmetric sets. Ann. Probab., 27(4):1922-1938, October 1999. URL: https://doi.org/10.1214/aop/1022874821.
  38. Rafał Latała and Krzysztof Oleszkiewicz. Small ball probability estimates in terms of width. Studia Mathematica, 169(3):305-314, 2005. URL: https://doi.org/10.4064/sm169-3-6.
  39. L. Leindler. On a certain converse of Hölder’s Inequality II. Acta Sci. Math. Szeged, 33:217-223, 1972. Google Scholar
  40. L. Lovász and S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures and Algorithms, 30(3):307-358, 2007. Google Scholar
  41. László Lovász. Combinatorial problems and exercises, volume 361. American Mathematical Soc., 1981. Google Scholar
  42. G. Margulis. Probabilistic characteristics of graphs with large connectivity. Prob. Peredachi Inform., 10:101-108, 1974. Google Scholar
  43. V.D. Milman. A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies. Funkcional. Anal. i Priložen, 5(4):28-37, 1971. Google Scholar
  44. R. O'Donnell and K. Wimmer. KKL, Kruskal-Katona, and monotone nets. In Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS), 2009. Google Scholar
  45. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  46. A. Prekopa. Logarithmic concave measures and functions. Acta Sci. Math. Szeged, 34:335-343, 1973. Google Scholar
  47. A. Prekopa. On logarithmic concave measures with applications to stochastic programming. Acta Sci. Math. Szeged, 32:301-316, 1973. Google Scholar
  48. Thomas Royen. A simple proof of the Gaussian correlation conjecture extended to multivariate gamma distributions. arXiv preprint, 2014. URL: http://arxiv.org/abs/1408.1028.
  49. L. Russo. On the critical percolation probabilities. Z. Wahrsch. werw. Gebiete, 56(2):229-237, 1981. Google Scholar
  50. M. Talagrand. How much are increasing sets positively correlated? Combinatorica, 16(2):243-258, 1996. Google Scholar
  51. Santosh S. Vempala. Learning convex concepts from gaussian distributions with PCA. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 124-130. IEEE Computer Society, 2010. Google Scholar
  52. M. Wainwright. Basic tail and concentration bounds, 2015. URL: https://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf.
  53. Artem Zvavitch. Personal communication, 2020. 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 Imprint Privacy Contact