Simons Symposium: Tuesday

This morning’s talks began with Daniel Kane, who told us about some exciting new decomposition/regularity theorems for low-degree polynomials of random $\pm 1$ bits. The motivation for his work is that although the known regularity lemmas and the known invariance principles are separately optimal, their combination is not. Knowing this, one can shoot for more adaptive/flexible polynomial decompositions which make up for the quantitatively poor parts of the invariance theorem. Daniel proved some new such decompositions. Putting everything together, this let him make some progress on the Gotsman–Linial Conjecture: he shows that if $f : \{-1,1\}^n \to \{-1,1\}$ is a degree-$d$ PTF then $\mathbb{NS}_\delta[f] \leq O_{d,\gamma}(1) \cdot \delta^{1/6 – \gamma}$ for any constant $\gamma > 0$.

Next up was Per Austrin. He told us about very recent work with the Cornell crypto group on the following pretty problem: Fix an unbiased $f : \{-1,1\}^n \to \{-1,1\}$. Now consider the following game: Input bits $x_1, x_2, …$ are set one at a time. For each, with probability $p$ you are allowed to choose if the bit is $1$ or $-1$. With probability $1-p$ you have no choice, and the bit is set uniformly at randomly. Your goal is to make the final output $x$ satisfy $f(x) = 1$. With optimal play, and for the worst $f$, how large can you guarantee ${\bf E}[f(\mathbf{x})]$ will be? The optimal guarantee is $p$ (the worst case is $f$ a dictator), and in fact this was proved earlier by Santha and Vazirani. However Per showed a new, simple, Fourier-based proof, which has the benefit of extending to give good results even for the case of $f : \{-1,1\}^n \to [-1,1]$ with fixed variance.

The next speaker was Luca Trevisan, who talked about his recent work with Lee and Oveis Gharan on “higher-order Cheeger inequalities”. The idea here is as follows: Let $G$ be an undirected graph and $\lambda_1 \leq \lambda_2 \leq \cdots$ the eigenvalues of its Laplacian. It is easy to show that $\lambda_k = 0$ if and only if $G$ has at least $k$ connected components. In the case of $k = 2$, “Cheeger’s Inequality” gives a ‘robust’ version of this fact: if $\lambda_2 \leq \epsilon$ then there are two disjoint sets of vertices (in fact, a partition) each of which has ‘edge-boundary’ at most $O(\sqrt{\epsilon})$. Luca’s work generalizes this to higher $k$: if $\lambda_k \leq \epsilon$ then there are $k$ disjoint sets of vertices (not necessarily a partition) each of which has ‘edge-boundary’ at most $\mathrm{poly}(k) \cdot \sqrt{\epsilon}$.

The last talk of the morning was by conference co-organizer Krzysztof Oleszkiewicz. Krzysztof described work (joint with Jendrej and Wojtaszczyk) regarding the FKN Theorem, which states that if $f : \{-1,1\}^n \to \{-1,1\}$ has $\mathbf{W}^1[f] \geq 1 – \delta$ then $f$ is $O(\delta)$-close to a 1-junta. Krzysztof gave a new elementary proof of this result, and also showed how to reach the optimal asymptotic closeness, $\delta/4 + O(\delta^2 \log(2/\delta))$. The key elementary lemma in his argument is: Let $\mathbf{X}$ and $\mathbf{Y}$ be independent (square-integrable) random variables, at least one of which is symmetric. Then $\mathbf{Var}[|\mathbf{X}+\mathbf{Y}|] \geq .359 \cdot \min(\mathbf{Var}[\mathbf{X}], \mathbf{Var}[\mathbf{Y}])$.

In the afternoon, Oded Regev spoke on the topic of ‘noncommutative Grothendieck inequalities’. Oded’s current research in this area is motivated by analyzing the value of quantum two-player one-round games. This research actually involves a strictly more general concept, ‘operator space Grothendieck inequalities’, but Oded was kind enough to limit his talk to a survey of just plain noncommutative Grothendieck. Recall that the usual Grothendieck inequality is concerned with maximizing $\sum_{i,j} A_{ij} x_i y_j$ over vectors $x, y$ satisfying $\|x\|_\infty, \|y\|_\infty \leq 1$. The theorem can be interpreted as saying that the natural semidefinite programming relaxation of this optimization problem has only a constant integrality gap. In the noncommutative generalization, one seeks to maximize $\sum_{i,j,l,\ell} A_{ijk\ell} X_{ij} Y_{k\ell}$ over matrices $X, Y$ with operator-norm at most 1. Again, it is a theorem that if one writes down a (somewhat carefully chosen) SDP relaxation, it has a constant integrality gap. (Curiously, the gap is known to be exactly 2; compare this to the usual Grothendieck case where the exact gap is not known!)

Our final speaker was Irit Dinur. She spoke about work in progress with Gillat Kol on ‘covering CSPs’. This is a variation on constraint satisfaction introduced by Venkat Guruswami and conference participants Johan Hastad and Madhu Sudan, in the early ’90s. Here there is a CSP and the task is to choose as few assignments as possible so that every constraint is satisfied by at least one chosen assignment. Graph and hypergraph coloring fits into this framework quite well. Irit described her exploration of the hardness landscape for covering CSPs: the challenging goal of finding a CSP for which distinguishing $O(1)$-coverability from $\Omega(\log n)$-coverability is hard, her results proving $O(1)$- versus $\omega(1)$-coverability hardness for $\mathsf{4XOR}$, and why the NAE predicate seems to be the ‘universal’ CSP in this context.

Per telling us how to tamper with Boolean functions

Irit lecturing on covering CSPs

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>