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$?

3 comments to Simons Symposium 2014 — Open Problems

  • Andris

    The second problem by Avi Wigderson does not make sense to me. Assume that we take f such that f(x)=1/2 for one input x\in\{0, 1\}^n, f(y)=-1/2 for some other input y and f(z)=0 everywhere else. Then, f satisfies (1)-(3) but the Fourier transform is quite well spread out (because it is spread out for point functions and taking a sum of two of them does not change it much).

    Is there a typo in the formulation? Or am I missing something?

    • I believe that, as written above, the second problem is simply not true. There should be a normalization factor, i.e., the problem should read “Prove that there exists $S \subseteq [n]$ of size $O(\log m)$ such that $|\hat f(S)| \geq \frac{m^{-O(1)}}{2^n}$”.

      • Li-Yang Tan

        Hi Andris and Gautam,

        Yes you are absolutely right, thanks for pointing this out! I’ve fixed it. (With this corrected formulation we see that without the condition on the size of $S$, there is clearly a Fourier coefficient of the desired magnitude.)

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>