Simons Symposium: Wednesday

This morning we had three speakers.

Hamed Hatami spoke about his recent work giving a generalization to boolean functions of the famous Friedgut(–Bourgain) theorem on sharp thresholds in graph properties. The question here is the following: Consider functions $f : \{0,1\}^n \to \{0,1\}$ where $\{0,1\}^n$ is thought of as having the $p$-biased measure, $p$ small. How can one characterize the set of functions with constant total influence? (For monotone functions, this is equivalent to characterizing the functions which have “coarse thresholds”, by the Russo–Margulis lemma.) For constant values of $p$, an early paper of Friedgut (similar to KKL) shows that having constant total influence is equivalent to being (close to) a junta. However the proof breaks down completely for the interesting case of $p = n^{-\Theta(1)}$. For such $p$, Friedgut gave a strong characterization in the special case of graph properties; Bourgain subsequently gave a partial characterization that works for general boolean functions. Hamed’s work extends Bourgain’s to obtain a complete characterization: constant total influence is equivalent to being (close to) a “pseudojunta”. The definition of “pseudojunta” is a tiny bit complicated, but this complication seems somewhat necessary. (Think about the case where $f$ is the graph property of containing a triangle; it has constant total influence but is not like any junta.) In fact, Hamed proved this characterization even for functions $f : X^n \to \{0,1\}$ where $X$ is any probability space; this takes notably more work.

The next speaker was El Mossel who spoke about Gaussian isoperimetric problems and their relationship with (Unique Games-)hardness. Suppose you want to partition Gaussian space into $q$ equal-volume pieces. First off, what partition minimizes the Gaussian surface area of the boundary? For $q = 2$ this is the classical isoperimetric problem in Gaussian space and is solved by a halfspace. For $q = 3$, it was recently proved by Cornelli et al. that the optimal solution is the $2$-dimensional, $120^\circ$ Y-shaped partition. The general conjecture here is that for higher $q$, an analogue of the Y based on a $q$-simplex is optimal. These questions about surface area are not precisely relevant for computational hardness, though; instead, one wants to look at the noise stability generalization: Suppose one chooses $k$ many $\rho$-correlated Gaussians; which partition maximizes the probability that all $k$ Gaussians fall in the same part? The Isaksson–Mossel Standard Simplex Conjecture (see the Open Problem list) says that the simplex solution is optimal for general $q$ and $k = 2$; one might also conjecture it for $k > 2$. Isaksson and Mossel have in fact proved this (unpublished) for $q = 2$ and $k = 3$; this has an application to hardness of the Max-3EQU CSP. Finally, El discussed the related question of robustness of the Gaussian Isoperimetric Inequality, where Gianchi et al. and Elchanan and Neeman have recent partial results.

Shachar lecturing

The last speaker of the day was Shachar Lovett. He spoke about joint work with Greg Kuperberg and Ron Peled on “existence of ‘rigid’ combinatorial objects”. A prime example of their results is a proof that there exist $2^{\mathrm{poly}(t)} n^{O(t)}$-size collections of $n$-permutations such that the uniform distribution on them is $t$-wise independent. Prior to their work, it was open whether polynomial-size was possible even for $4$-wise independence. Establishing this result involves investigating a more general question: Let $\Phi$ be an $N \times n$ matrix of integers in $[-n, n]$ such that the group of symmetries of $\textrm{im}(\Phi)$ (a subgroup of $S_N$) is transitive. Is it true that there are $\mathrm{poly}(n)$ rows of $\Phi$ whose average is equal to the overall average of $\Phi$’s rows? Shachar can’t prove this, but he can do it assuming certain extra hypotheses: that $\textrm{im}(\Phi)$ is “locally decodable”, or an “LDPC”. The main tools used in the work are Fourier analysis over ${\mathbb R}/{\mathbb Z}$ and “local” Central Limit Theorems.

In the afternoon we had a lovely hike around Francis Bay and the Annaberg sugar mill ruins.

Annaberg sugar mill ruins

Irit, Rocco, Daniel, and Krzysztof peering at wildlife on the hike

6 comments to Simons Symposium: Wednesday

Leave a Reply

  

  

  

You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>