|
|
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$?
|
|
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}$”.
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.)