Simons Symposium 2014 — Open Problems

  • (Boaz Barak) Is there an efficient algorithm for finding sparse vectors in subspaces $V\subseteq \mathbb{R}^n$? Here by sparsity Boaz has in mind vectors $v\in V$ whose number of non-zero coordinates is $o(n)$, though he is also interested in various approximations including \[  \mathbb{E}\big[v_i^4\big] \gg \mathbb{E}\big[v_i^2\big]^2. \]Relatedly, what can we say about polynomials $p$ over Gaussian space that satisfy \[ \mathbb{E}\big[p(\boldsymbol{x})^4\big] \gg \mathbb{E}\big[p(\boldsymbol{x})^2\big]^2?\] Must $p$ be correlated to the product of linear functions? (Rafał mentions that this is true for quadratic polynomials $p$.) Finally, what can we say about the structure of subsets $S \subseteq \mathbb{F}_2^n$ that have the “small doubling” property $|S+S| \ll |S|^2$?
  • (Ehud Friedgut) A $t$-coset in $S_n$ is a coset of the stabilizer of $t$ points. Is every partition of $S_n$ into $t$-cosets a refinement of a partition into $(t-1)$-cosets?
  • (Avi Wigderson) Let $T \in \mathbb{R}^{n\times n\times n\times n}$ be a 4-dimensional tensor $T = \sum \alpha_{ijk\ell} x_i y_j z_k w_\ell$. Define $\mathrm{rank}_{xy,zw}(T)$ to be the rank of the $n^2\times n^2$ matrix whose entry in the $(i,j)$-th row and $(k,\ell)$-th column is $\alpha_{ijk\ell}$, and likewise $\mathrm{rank}_{yz,wx}(T)$ to be the rank of the matrix whose entry in the $(j,k)$-th row and $(\ell,i)$-th column is $\alpha_{ijk\ell}$. The problem is the find an explicit tensor $T$ such that whenever $T = T_1 + T_2$ and $\mathrm{rank}_{xy,zw}(T_1) \le r$ and $\mathrm{rank}_{yz,wx}(T_2) \le r$, then $r \ge n^{1+\epsilon}$. Avi suggests the super-simple candidate $T_0 = \sum_{i,j} x_i y_j z_i w_j$. This has implications for lower bounds in non-commutative computation, and in particular, such an explicit tensor would yield an exponential lower bound against the size of non-commutative arithmetic circuits computing permanent; see Avi’s paper with Pavel Hrubeš and Amir Yehudayoff for more details.
  • (Raghu Meka) Let $A_1,\ldots,A_n \in \mathbb{R}^{n\times n}$ be symmetric matrices satisfying $\| A_i \| \le 1$ for all $i\in [n]$. Prove that\[ \Pr\Big[\Big\| \sum \boldsymbol{g}_i A_i \Big\| \le 1000\sqrt{n} \Big] \ge 2^{-\Omega(n)}, \]where the probability is with respect to the $\boldsymbol{g}_i$’s which are independent standard Gaussians. An affirmative answer would have applications to the conjectured Matrix Spencer Theorem.
  • (Yuval Filmus) Let $f:\{0,1\}^n \to [-1,1]$ be a bounded function over the hypercube, and suppose the Fourier degree of $f$ is at most $d$. Define the $L_1$-influence of $f$ to be\[ \mathrm{Inf}[f] := \sum_{i=1}^n \mathop{\mathbb{E}}_{\boldsymbol{x}\in\{0,1\}^n} \bigg[\bigg| \frac{f(\boldsymbol{x})-f(\boldsymbol{x}\oplus e_i)}{2}\bigg|\bigg]. \]Is it true that $\mathrm{Inf}[f] \le d$ for all $f$ (which would be tight by considering the parity function on $d$ variables)? Recent work of Artūrs Bačkurs and Mohammad Bavarian prove a bound of $O(d^3\log d)$, answering a question of Aaronson and Ambainis. This has been improved by Yuval (in joint work with Hamed Hatami, Guy Kindler, and Elchanan) to $d^2$. (Note that for Boolean-valued $f: \{0,1\}^n \to \{-1,1\}$ this definition of $L_1$-influence agrees with the slightly more standard notion of influence (i.e. “$L_2$-influence”), and in this case we do indeed have the bound $\mathrm{Inf}[f] \le \mathrm{deg}[f]$.)
  • (Yuval Peres) Let $A \subseteq \mathbb{Z}_n$ and suppose $|A| = \Theta(n^{\alpha})$ for some $\alpha$. Define the quantity\[ K_A := \min\left\{ k \colon \exists\, x_1,\ldots,x_k \text{ such that } \bigcup_{i=1}^k\, x_i + A = \mathbb{Z}_n\right\}.\]It is known that\[ n^{1-\alpha} \lesssim K_A \lesssim n^{1-\alpha}\log n, \]and there are examples of sets $A$ showing that both inequalities are tight. Yuval’s question is: what is the magnitude of $K_A$ for a random set $A$? Ben Green has shown that for all $\alpha > 1/2$, there exists a constant $C_\alpha$ such that $K_A \ge C_\alpha n^{1-\alpha}\log n$ for a random set $A$.
  • (Raghu Meka) Let $G$ be the set of all permutations on $n^2$ elements, and consider the action of this group on balanced strings $x\in \{0,1\}^{n^2}$.  Let $S$ be an expanding set of generators for $G$ and consider a random walk of length $t = O(\log(n/\epsilon))$ on $\{0,1\}^{n^2}$ obtained by applying random elements of $S$ iteratively on a fixed balanced string in $\{0,1\}^{n^2}$. If $\boldsymbol{y}\in \{0,1\}^{n^2}$ is the resulting string after such a walk (with worst-case starting point), is it true that $\sum_{i=1}^n \boldsymbol{y}_i$ is $O(\epsilon)$ close in TV-distance to $\mathrm{Bin}(n,1/2)$? You can change $n^{2}$ to $n^{100}$ if you think it helps.
  • (Thomas Vidick) Consider $m$ equations $\varphi_k(x) = x_ix_j$ and signs $\epsilon_k \in \{-1,1\}^n$ for $k \in [m]$. The Max-2LIN problem of computing\[ \mathop{\max_{x_i\in\mathbb{R}}}_{x_i^2 = 1} \left\{\frac1{m} \sum_{k=1}^m \mathbb{1}[\varphi_k(x) = \epsilon_k]\right\} \]is NP-hard. However, when the variables $x_i \in \mathbb{R}^n$ are replaced with orthogonal matrices in the following way:\[ \mathop{\max_{X_i\in\mathbb{R}^{d\times d}}}_{X_i^2 = \mathrm{Id}} \left\{\frac1{m} \sum_{k=1}^m \mathbb{1}\Big[\frac1{d}\mathrm{Tr}(\varphi_k(X)) = \epsilon_k\Big]\right\},\]this quantity can be computed in polynomial time using SDPs. Can the same be done for other predicates, e.g. $\varphi_k(X) = X_i X_j X_k$?
  • (Li-Yang Tan) Find an explicit $f:\{0,1\}^n\to\{0,1\}$ such that any $g:\{0,1\}^n\to\{0,1\}$ satisfying $\Pr[f(\boldsymbol{x})\ne g(\boldsymbol{x})] \le \epsilon$ requires DNFs of size $\Omega_\epsilon(2^n/\mathrm{poly}(n))$ to compute. (This is true for a random function $f$.) Ryan and Karl Wimmer proved that MAJORITY can be $\epsilon$-approximated by a DNF of size $2^{O_\epsilon(\sqrt{n})}$; subsequently Eric Blais and I showed that PARITY can be $\epsilon$-approximated by a DNF of size $2^{(1-2\epsilon)n} = O_\epsilon(2^n/\mathrm{exp}(n))$. A candidate explicit hard function $f$ for this problem is a random symmetric function.
  • (Ryan O’Donnell, sharing an open problem due to Mendel and Naor) Let $f:\{-1,1\}^n \to \mathbb{R}$ where $\hat{f}(S) = 0$ for all $|S| < k$. The inequality \[ \| T_\rho f \|_2 \le \rho^k \|f\|_2, \] is a straightforward consequence of the Fourier expansion $T_\rho f(x) = \sum_{S\subseteq [n]} \rho^{|S|}\hat{f}(S) \chi_S(x)$, but how about analogous inequalities for higher norms?  For example, is it true that\[ \| T_\rho f \|_4 \le \rho^{0.001k} \| f\|_4? \]The problem is open even for $k=1$!
  • (Avi Wigderson) Let $f:\{0,1\}^n \to [-1,1]$ be a bounded function satisfying the three conditions: (1) $\mathbb{E}[f(\boldsymbol{x})] = 0$, (2) $\sum |f(x)| = 1$, and (3) $|\mathrm{supp}(f)| \le m$. Prove that there exists $S \subseteq [n]$ of size $O(\log m)$ such that $|\hat{f}(S)| \ge m^{-O(1)}2^{-n}$. Avi and Amir Yehudayoff prove a lower bound of $|\hat{f}(S)| \ge m^{-O(\log m)}2^{-n}$ in this paper.
  • (Yuval Peres) Let $A$ be a stochastic, symmetric positive-definite matrix. For a given $k \in \mathbb{Z}^+$, let $(i_k, j_k)$ be the position of the smallest entry of $A^k$. Conjecture: for all $\ell < k$ it holds that $A^\ell[i_k, j_k] \leq A^k[i_k, j_k]$. In some sense, “if it’s very hard to get from vertex $i$ to vertex $j$ in $k$ steps, then it’s even harder to do it in fewer steps”. The conjecture is open even for $3 \times 3$ matrices.
  • (Krzysztof Oleszkiewicz) Let $F$ be a normed linear space, and say that $A \subseteq F$ is $\delta$-separate if $\| x – y \|\ge \delta$ for all distinct $x,y\in A$. Let $A,B \subseteq F$ be two non-empty, $1$-separate subsets.  Prove that there always exists $C \subseteq A+B$ of size $|C| \ge |A|+|B|-1$ such that $C$ is $\delta$-separate for some universal constant $\delta > 0$.
  • (Rafał Latała) [Might not have transcribed this one correctly...] Let $\boldsymbol{X}_t$ be a stochastic process and suppose $|T| \leq \exp(p)$. Then it’s not hard to show that
    \[
    {\bf E}[\max_{t \in T} \boldsymbol{X}_t] \lesssim \max\{{\bf E}[|\boldsymbol{X}_t|^p]^{1/p}\}.
    \]
    The question is when this can be reversed. In other words, continuing to assume $|T| \leq \exp(p)$, suppose that for all $t, s \in T$ it holds that ${\bf E}[|\boldsymbol{X}_t - \boldsymbol{X}_s|^p]^{1/p} \geq C$. Under what circumstances do we also have ${\bf E}[\max_{t \in T} \boldsymbol{X}_t] \gtrsim C$? It seems that for Gaussian processes it follows by Sudakov Minoration. What about the case where $\boldsymbol{X}_t = \sum_{i=1}^n t_i \boldsymbol{Y}_i$, where $\boldsymbol{Y}$ is uniform on some convex set $K \subseteq \mathbb{R}^n$? In this case, if $K$ is a cube, the implication follows from work of Talagrand.
  • (Boaz Barak) Prove that there exists $\epsilon,\delta > 0$ such that for every graph $G$ on $N$ vertices containing at least $\mu N^3$ many triangles, the number of $K_{2,2,2}$’s in $G$ is at least $\delta\mu^{8-\epsilon}N^6$. (Iterated Cauchy-Schwarz gives a lower bound of $\mu^8N^6$.) There are potential applications to lower bounds in the NOF model of communication complexity.
  • (Avi Wigderson, sharing an open problem due to him and Oded Goldreich) Suppose we are given an efficiently computable $f:\{0,1\}^n \to\{ \mathrm{Good},\mathrm{Bad}\}$ (e.g. $f$ is computable by a constant-degree polynomial), with the promise that $|f^{-1}(\mathrm{Bad})| \le 2^n/3$. Our goal is to efficiently find an $x\in f^{-1}(\mathrm{Good})$. (Avi refers to this as the problem of “finding hay in the haystack”.)  Certainly we can easily accomplish this with a randomized algorithm; the key is to do it deterministically. As it turns out this derandomization problem remains equivalent even if we are given the significantly stronger promise that $|f^{-1}(\mathrm{Bad})| \le 2^{n^{\epsilon}}$. Avi and Oded’s question is: what if $|f^{-1}(\mathrm{Bad})| \le n^{\log n}$? Note that there is a trivial deterministic algorithm that runs in quasi-polynomial time, since any set of $n^{\log n} + 1$ many inputs must contain an $x$ such that $f(x) = \mathrm{Good}$.
  • (Raghu Meka) Let $f_1,\ldots,f_n$ be linear threshold functions where $f_i$ does not depend on $x_i$ for all $i\in [n]$. Is it true that \[ \mathop{\mathbb{E}}_{\boldsymbol{x}\sim\{-1,1\}^n}\bigg[\bigg| \sum_{i=1}^n \boldsymbol{x}_i f_i\bigg|\bigg]^2 = O(n)? \] An affirmative answer would have applications to the Gotsman–Linial conjecture on the average sensitivity of polynomial threshold functions. For arbitrary Boolean functions $f_1,\ldots,f_n$, where again $f_i$ does not depend on $x_i$ for all $i\in [n]$, it is known that \[ \mathop{\mathbb{E}}_{\boldsymbol{x}\sim\{-1,1\}^n}\bigg[\bigg| \sum_{i=1}^n \boldsymbol{x}_i f_i\bigg|\bigg]^2 \le 2\bigg(\sum_{i=1}^n \mathrm{Inf}[f_i]\bigg) + n,\]and there are examples showing that this is tight.
  • (Yuval Peres) Let $G$ be a transitive graph, and consider edge percolation on $G$ with parameter $p$ (i.e. each edge is present with probability $p$). Define the quantity \[ S(p) := \mathop{\mathbb{E}}_p[|\mathcal{C}(v)|],\] where $v$ is an arbitrary vertex in $G$ and $\mathcal{C}$ is the component containing $v$. Is the logarithmic derivative $S’(p)/S(p)$ unimodal in $p$?

Simons Symposium 2014 — Day 4

[Editor's note -- just a reminder that these daily updates are almost entirely thanks to Li-Yang Tan.]

The first speaker of the day was Sergey Bobkov, who spoke about concentration on the cube and its relationship with various isoperimetric problems, including highlights of his own work.
Continue reading Simons Symposium 2014 — Day 4

Simons Symposium 2014 — Day 3

The first speaker of the day was Subhash Khot, who discussed his recent work with Madhur Tulsiani and Pratik Worah giving a complete characterization of the approximation resistance of constraint satisfaction problems (CSPs) under Subhash’s Unique Games Conjecture (UGC).
Continue reading Simons Symposium 2014 — Day 3

Simons Symposium 2014 — Day 2

The second day began with Tom Sanders speaking about the Bourgain-Green sumset problem in additive combinatorics, including some of his own work on the problem.
Continue reading Simons Symposium 2014 — Day 2

Simons Symposium 2014 — Day 1

Li-Yang here.

Avi Wigderson kicked off this year’s symposium with a talk describing recent joint work with Dimitri Gavinsky, Or Meir, and Omri Weinstein attacking one of the central open problems in computational complexity: does ${\mathsf P} = \mathsf{NC}^1$, or in words, can every sequential computation be efficiently parallelized?
Continue reading Simons Symposium 2014 — Day 1

Simons Symposium 2014 — Discrete Analysis: Beyond the Boolean Cube

I’m pleased to announce that this week we’ll be reporting on the 2014 Simons Symposium — Discrete Analysis: Beyond the Boolean Cube. This is the second of three biannual symposia on Analysis of Boolean Functions, sponsored by the Simons Foundation. You may remember our reports on the 2012 edition which took place in Caneel Bay, US Virgin Islands. This year we’re lucky to be holding the symposium in Rio Grande, Puerto Rico.

The Beach

Room with a view

I’m also happy to report that we will have guest blogging by symposium attendee Li-Yang Tan. This year’s talk lineup looks quite diverse, with topics ranging from the Bernoulli Conjecture Theorem to Fourier analysis on the symmetric group, to additive number theory. Stay tuned!

§11.3: Borell’s Isoperimetric Theorem

If we believe that the Majority Is Stablest Theorem should be true, then we also have to believe in its “Gaussian special case”. Let’s see what this Gaussian special case is.
Continue reading §11.3: Borell’s Isoperimetric Theorem

§11.2: Hermite polynomials

Having defined the basic operators of importance for functions on Gaussian space, it’s useful to also develop the analogue of the Fourier expansion.
Continue reading §11.2: Hermite polynomials

§11.1: Gaussian space and the Gaussian noise operator

We begin with a few definitions concerning Gaussian space.
Continue reading §11.1: Gaussian space and the Gaussian noise operator

The book is available for pre-order

I’m happy to announce that the book is very nearly completed. In fact, you can pre-order a copy now, either directly from Cambridge University Press, or from Amazon (currently with a 10% discount). If all goes well, the book will become physically available at the end of May. Fairly soon thereafter I will also make a pdf “final draft” version freely available here at the website.

In the meantime, I will continue to serialize the final chapter (Chapter 11) as usual over the next month. In fact, I had to trim and glue together the planned Chapters 11 and 12. Also, as mentioned earlier, I dropped a chapter on Additive Combinatorics that would have gone between Chapters 8 and 9, although its “highlight”, Sanders’s Theorem, is here on the blog. Oh well, I had to wrap this project up at some point; at least you’ll have an idea of what will be in the 2nd Edition. :)