Convex Influences.
A. De and S. Nadimpalli and R. Servedio.
13th Innovations in Theoretical Computer Science Conference (ITCS), 2022, pp. 53:1-53:21.


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\}^n \to \{-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 Poincare 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,1\}^n$. Taken as a whole, our results extend the emerging analogy between symmetric convex sets in Gaussian space and monotone Boolean functions from $\{-1,1\}^n$ to $\{-1,1\}$.

pdf of conference version

pdf of full version on arxiv


Back to main papers page