Abstracts

Functional Inequalities in Discrete Spaces with Applications

Monday, September 30th, 2013

A Structure Theorem for Boolean Functions with Small Total Influences
9:00 am–9:50 am
Speaker: Hamed Hatami, McGill University

We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sharp thresholds. This result generalizes the core of Friedgut's seminal work on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces, and improves the result of Bourgain in his appendix to Friedgut's paper.

PDF icon A Structure Theorem for Boolean Functions with Small Total Influences (slides)
On Mimicking Rademacher Sums
10:20 am–11:10 am
Speaker: Krzysztof Oleszkiewicz, University of Warsaw

Approximation in L^1 of a Rademacher sum (defined as a linear function on the discrete cube) by a function without low frequencies will be discussed.

PDF icon On Mimicking Rademacher Sums (slides)
Maximal Inequalities on the Hypercube
1:30 pm–2:20 pm
Speaker: Alexandra Kolla, University of Illinois, Urbana-Champaign

In this talk, we establish a dimension-free ell_2 maximal inequality for spherical means on the Hypercube graph {0,1}^n. We explain possible connections to the notorious Unique Games Conjecture.

Combinatorially, this inequality implies the following stronger alternative to the union-bound technique: Assume that we have a binary function f (values 0,1) on the n-dimensional hypercube Hn, with N=2^n vertices. Think of the set X={xin Hn : f(x)=1} as the set vertices that a malicious adversary "spoils". Assume |X|adversary can only spoil up to epsilon fraction of the vertices. Fix a threshold lambda>epsilon. Say a (hamming) sphere S(x,r) or radius r around a point x is "bad" if the adversary has spoiled more than lambda fraction of the points in the shpere. We call a point x "ruined" if there exists a radius r for which the sphere S(x,r) around x is bad. Our maximal inequality implies that for every lambda, there is an absolute constant epsilon (which does not depend on the dimension n) that if the adversary spoils at most epsilon fraction of the points then the "ruined" set is a strict subset of the hypercube. Note that applying a union-bound over radii instead, we would not get any useful inequality for the size of the ruined set.

PDF icon Maximal Inequalities on the Hypercube (slides)
Variants of Parseval's Formula and the Grothendieck Inequality
2:50 pm–3:40 pm
Speaker: Ron Blei, University of Connecticut

The Grothendieck inequality can be equivalently viewed as a Parseval-like formula: a particular integral representation of the dot product in Euclidean space. We discuss this view in a setting of harmonic analysis on dyadic groups, and, specifically, the role of Riesz product amalgams therein.

PDF icon Variants of Parseval's Formula and the Grothendieck Inequality (slides)
On Correlation Inequalities for Monotone Subsets of the Discrete Cube
4:10 pm–5:00 pm
Speaker: Nathan Keller, Bar-Ilan University

The well-known correlation inequality of Harris (1960) asserts that any two monotone subsets of the discrete cube are non-negaitvely correlated. In 1996, Talagrand established a lower bound on this correlation in terms of how much the two subsets are influenced by the same coordinates. Talagrand's result (or the main lemma used in its proof) was central in the proof of several later results, such as the BKS noise sensitivity theorem and a lower bound on the boundary of monotone subsets of the discrete cube.

While Talagrand's result is known to be tight, with several diverse examples of tightness, all known examples of this type are "symmetric", in the sense that the influence of each coordinate is roughly the same for the two examined subsets. In particular, there is no example of tightness in which one of the subsets is balanced while the other is of a small measure.

In this talk we discuss lower bounds similar to Talagrand's one, which appear to be stronger in the "asymmetric" cases, and propose a conjectured bound which will unify Talagrand's bound with the newly obtained ones.

Video was unavailable for this talk. We apologize for any inconvenience.

Tuesday, October 1st, 2013

Concentration Inequalites in Learning with Kernels
9:00 am–9:50 am
Speaker: Devdatt Dubhashi, Chalmers University of Technology

Concentration of measure is becoming an indispensable tool in many machine learning applications. We will give several examples of the use of such inequalities in the area of learning with kernels and support vector machines (SVMs).

PDF icon Concentration Inequalites in Learning with Kernels (slides)
Concentration Inequalities for Non-Lipschitz Functions
10:20 am–11:10 am
Speaker: Paweł Wolff, University of Warsaw

Classical concentration inequalities allow to control deviation of a Lipschitz function from its mean. In this talk I shall present a method based on functional inequalities which allows to handle the class of smooth functions with bounded derivatives of higher order (so, in particular, multivariate polynomials). When combined with Latała’s estimates for Gaussian chaoses, it leads to exponential-type tail estimates for smooth functions in random vectors which satisfy e.g. the logarithmic Sobolev inequality. I will also present related estimates for polynomials in independent sub-Gaussian random variables. Applications to linear eigenvalue statistics of random matrices and a problem of subgraph counts in random graphs will also be discussed.

Based on joint work with R. Adamczak (University of Warsaw).

PDF icon Concentration Inequalities for Non-Lipschitz Functions (slides)
Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
11:40 am–12:30 pm
Speaker: Yuval Peres, Microsoft Research Redmond

Let f(X_1 , ..., X_n} be a a Lipschitz function of n binary random variables.

If the variables X_i are independent, it is classical that f satisfies a Gaussian concentration inequality.

We show that such an inequality holds for a large class of negatively dependent variables known as strong Rayleigh. (This inequality is easy and well known if f is linear under weaker hypothesis on the X_i, but new for nonlinear f).The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; the most familiar example is the uniform spanning tree. For instance, any Lipschitz function of the edges of a uniform spanning tree in a given graph (e.g., the number of leaves) satisfies a Gaussian concentration inequality. This answers a question posed by Elchanan Mossel. (Joint work with Robin Pemantle).

On the Suprema of Bernoulli Processes
2:25 pm–3:15 pm
Speaker: Rafał Latała, University of Warsaw

We present a positive solution to the so-called Bernoulli Conjecture concerning the characterization of sample boundedness of Bernoulli processes. We also discuss some applications and related open problems. The talk is based on the joint work with Witold Bednorz.

PDF icon On the Suprema of Bernoulli Processes (slides)
Spectral Gap of a Kinetically Constrained Spin Model on Trees: Power Law Scaling at Criticality
3:45 pm–4:35 pm
Speaker: Cyrille Roberto, Université Paris Ouest

On the rooted k-ary tree we consider a 0-1 kinetically constrained spin model in which the occupancy variable at each node is re-sampled with rate one from the Bernoulli(p) measure iff all its children are empty.

For this process the following picture was conjectured to hold. As long as p is below the percolation threshold p_c=1/k the process is ergodic with a finite relaxation time while, for p > p_c, the process on the infinite tree is no longer ergodic and the relaxation time on a finite regular sub-tree becomes exponentially large in the depth of the tree. At the critical point p=p_c the process on the infinite tree is still ergodic but with an infinite relaxation time. Moreover, on finite sub-trees, the relaxation time grows polynomially in the depth of the tree.

The conjecture was proved by F. Martinelli and C. Toninelli except at criticality. In this talk, based on a joint work with N. Cancrini, F. Martinelli and C. Toninelli, we shall present a proof of the conjecture at the critical point.

Wednesday, October 2nd, 2013

Discrete Ricci Curvature via Convexity of the Entropy
9:00 am–9:50 am
Speaker: Jan Maas, University of Bonn

We present a notion of Ricci curvature that applies to Markov chains on discrete spaces. This notion is inspired by the seminal work of Lott, Sturm and Villani, who developed a synthetic notion of Ricci curvature for geodesic spaces based on convexity of the entropy along 2-Wasserstein geodesics.

In the discrete setting the role of the 2-Wasserstein metric is taken over by a different metric, having the property that continuous time Markov chains are gradient flows of the entropy.

This approach allows us to obtain discrete analogues of results by Bakry–Emery and Otto–Villani.

This is joint work with Matthias Erbar (Bonn).

PDF icon Discrete Ricci Curvature via Convexity of the Entropy (slides)
Displacement Convexity of Entropy on Graphs
10:20 am–11:10 am
Speaker: Prasad Tetali, Georgia Institute of Technology

We introduce the notion of an interpolating path on the set of probability measures on finite graphs. Using this notion, we first prove a displacement convexity property of entropy along such a path and derive Prekopa-Leindler type inequalities, a Talagrand transport-entropy inequality, as well as log-Sobolev type inequalities in discrete settings. To illustrate through examples, we apply our results to the complete graph and to the hypercube for which our results are optimal—by passing to the limit, we recover the classical log-Sobolev inequality for the standard Gaussian measure with the optimal constant. Many questions remain open. This is joint work with Nathael Gozlan, Cyril Roberto and Paul-Marie Samson.

On Graph Spectra and Small Set Expansion
11:40 am–12:30 pm
Speaker: Prasad Raghavendra, UC Berkeley

Approximating expansion of small sets in graphs is a computational problem of great interest due to its connections to the unique games conjecture. In this talk, we will survey some recent developments that connect the spectrum of graphs to edge expansion of small sets in them. Specifically, we will discuss the following results:

  1. Higher Order Cheeger Inequalities: These are analogues of the classical Cheeger's inequality that connect the higher eigenvalues of the graph to the corresponding combinatorial problem of decomposing a graph in to several sets of small sparsity. In turn, these yield a direct connection between higher eigenvalues and expansion of small sets in graphs.
  2. Graphs with Large Threshold Rank: The complexity of small set expansion problem is directly tied to the number of large eigenvalues of the graph. In fact, for the small set expansion to be computationally intractable, there must exist small set expanders that have up to polynomially many large eigenvalues. While the existence of such graphs still remains open, a recent construction called the `short code' achieves quasi polynomially many eigenvalues. This is achieved by creating a subgraph of the noisy hypercube graph that inherits the spectral and hypercontractive properties but is on much fewer vertices.
PDF icon On Graph Spectra and Small Set Expansion (slides)
Two Generalizations of Cheeger's Inequality
2:25 pm–3:15 pm
Speaker: Luca Trevisan, Stanford University

The Cheeger inequality in graphs relates the second smallest eigenvalue of the Laplacian of the graph to the conductance of the graph. It has applications to approximation algorithms, as an analysis of the "sweep" partitioning algorithm; to the construction of expander graphs; and to the analysis of random walks in graphs. We describe a generalization that relatex the k-th smallest eigenvalue of the Laplacian to the "order-k" conductance of a graph, and discuss its connection to the analysis of spectral partitioning algorithms. We also show a tighter Cheeger inequality for graphs of bounded "threshold rank," giving an improved analysis of the sweep algorithm in such graphs.

On Hyperboundedness and Spectrum of Markov Operators
3:45 pm–4:35 pm
Speaker: Laurent Miclo, University of Toulouse

Consider an ergodic Markov operator $M$ reversible with respect to a probability measure $mu$ on a general measurable space. We will show that if $M$ is bounded from ${cal L}^2(mu)$ to ${cal L}^p(mu)$, where $p>2$, then it admits a spectral gap. This result answers positively a conjecture raised by Høegh-Krohn and Simon in a semi-group context. The proof is based on isoperimetric considerations and especially on Cheeger inequalities of higher order for weighted finite graphs recently obtained by Lee, Gharan and Trevisan. In general there is no quantitative link between hyperboundedness and spectral gap (except in the situation investigated by Wang), but there is one with another eigenvalue. In addition, the usual Cheeger and Buser inequalities will be extended to higher eigenvalues in the compact Riemannian setting.

PDF icon On Hyperboundedness and Spectrum of Markov Operators (slides)

Thursday, October 3rd, 2013

A Removal Lemma for Kneser Graphs and Product Graphs
9:00 am–9:50 am
Speaker: Ehud Friedgut, Weizmann Institute

The celebrated triangle removal lemma for graphs (Ruzsa-Szemeredi) has important applications in extremal graph theory and additive/combinatorial number theory (e.g., it implies Roth's theorem on sets of integers with no 3 term arithmetic progression). It can be interpreted as stating that in a certain hypergraph any set that spans few edges can be made independent by removing few vertices.

We prove a similar statement "one level down," in (certain) graphs, e.g. Kneser graphs and certain product graphs. As a corollary we strengthen the characterization of intersecting families of sets given by Dinur and Friedgut, and the characterization of independent sets in product graphs by Dinur Friedgut and Regev.

The techniques we use build on the aforementioned result of DFR (that uses the famous MOO (Mossel, O'Donnell, Oleszkiewicz) invariance principle as an engine), and also follow Fox's relatively new proof of the triangle removal lemma.

Joint work with Oded Regev.

Approximations of Submodular, XOS and Self-Bounding Functions by Juntas
10:20 am–11:10 am
Speaker: Jan Vondrák, IBM Almaden

Motivated by applications in machine learning, we investigate the approximability of several classes of real-valued functions on {0,1}^n by juntas (functions of a small number of variables). Our goal is to approximate a target function, with range normalized to [0,1], within l_2-error epsilon over the uniform distribution. Our two main results are as follows.

Every submodular function is epsilon-close to a function of O(1/epsilon^2 log (1/epsilon)) variables. This result is proved using a "boosting lemma" by Goemans and Vondrak. We note that Omega(1/epsilon^2) variables are necessary even for linear functions.

Every XOS, self-bounding or more generally low average l1-sensitivity function is epsilon-close to a function of 2^{O(1/epsilon^2)} variables. This result is proved using the hypercontractive inequality, similarly to Friedgut's theorem for boolean functions . We show that 2^{Omega(1/epsilon)} variables are necessary even for XOS functions.

Joint work with Vitaly Feldman.

PDF icon Approximations of Submodular, XOS and Self-Bounding Functions by Juntas (slides)
Noise Stability and Central Limit Theorem for Random Effective Resistance
11:40 am–12:30 pm
Speaker: Raphaël Rossignol, University of Grenoble

We investigate the (generalized) Walsh decomposition of point-to-point effective resistances on countable random electric networks with i.i.d resistances. We show that it is concentrated on low levels, and thus point-to-point effective resistances are uniformly stable to noise. For graphs that satisfy some homogeneity property, we show in addition that it is concentrated on sets of small diameter. As a consequence, we compute the right order of the variance and prove a central limit theorem for the effective resistance through the discrete torus of side length n, when n goes to infinity.

PDF icon Noise Stability and Central Limit Theorem for Random Effective Resistance (slides)
Strong Noise Sensitivity and Random Graphs
2:25 pm–3:15 pm
Speaker: Jeffrey Steif, Chalmers University of Technology

The noise sensitivity of a Boolean function describes its likelihood to flip under small perturbations of its input. Introduced in the seminal work of Benjamini, Kalai and Schramm (BKS), it was there shown to be governed by the first level of Fourier coefficients in the central case of monotone functions at a constant critical probability.

Here we study noise sensitivity and a natural stronger version of it, addressing the effect of noise given a specific witness in the original input. Our main context is the Erdös-Renyi random graph, where for most interesting properties, the relevant value of the probability of the input goes to 0 polynomially fast in the number of variables and hence BKS does not apply. For a number of interesting properties, we can determine quantitative versions which yield the precise level of noise necessary in order to have an effect. This is joint work with Eyal Lubetzky.

PDF icon Strong Noise Sensitivity and Random Graphs (slides)
Majority is Stablest for Dependent Variables
3:45 pm–4:35 pm
Speaker: Joe Neeman, UC Berkeley

The "majority is stablest" theorem says that a low-influence function of independent binary variables cannot be more noise stable than the simple majority function. We prove an extension of this theorem that allows for certain non-independent variables, such as variables distributed according to an Ising model. Our extension also allows us to study some new continuous limits. For example, we give a theorem comparing the noise sensitivity of log-concave variables with the noise sensitivity of Gaussian variables.

This is joint work with Elchanan Mossel.

Friday, October 4th, 2013

A Two-Sided Estimate for the Gaussian Noise Stability Deficit
9:00 am–9:50 am
Speaker: Ronen Eldan, Microsoft Research

We give a novel short proof of Borell's Gaussian noise stability inequality, based on stochastic calculus. Moreover, we prove an almost tight, two-sided, dimension-free robustness estimate for this inequality: by introducing a new metric to measure the distance between the set A and its corresponding half-space H (namely the distance between the two centroids), we show that the deficit between the noise stability of A and H can be controlled from both below and above by essentially the same function of the distance, up to logarithmic factors.

As a consequence, we also manage to get the conjectured exponent in the robustness estimate proven by Mossel-Neeman, which uses the total-variation distance as a metric. In the limit where the correlation goes to 1, we get an improved dimension free robustness bound for the Gaussian isoperimetric inequality. Our estimates are also vali d for a the more general version of stability where more than two correlated vectors are considered.

Reversing Hypercontractivity
10:20 am–11:10 am
Speaker: Elchanan Mossel, UC Berkeley

I will discuss reverse-hyper-contraction and some applications.

Influences in Gaussian Space
11:40 am–12:30 pm
Speaker: Arnab Sen, University of Minnesota

The notion of influences in the Boolean cube has a natural extension to Gaussian space. In this talk, I will explain the how this new definition of influences leads to the analogs of several fundamental results of discrete harmonic analysis including the Kahn–Kalai–Linial bound, the threshold phenomenon for monotone events and the Benjamini–Kalai–Schramm noise sensitivity theorem in the Gaussian setup.

This talk is based on joint work with Nathan Keller and Elchanan Mossel.

PDF icon Influences in Gaussian Space (slides)