Simons Symposium: final open problems

As mentioned, we had one more open problems session on Thursday.

First, we presented Allison Lewko’s problem: prove that the symmetric $f : \{-1,1\}^n \to \{-1,1\}$ which minimizes $\mathbf{I}[f]/\mathbf{Var}[f]$ is Majority (assuming $n$ odd). Daniel Kane had some ideas on how to solve this, so I hope he and Allison will work it out in the near future.

Next, Avi presented the “Correlation Bounds for Polynomials” problem, Oded presented the “Symmetric Gaussian Problem”, and Jelani presented the “$k$-wise Independence for PTFs” problem.

Luca then described the problem of fooling DNF with $\epsilon$-biased distributions. In joint work with De, Etesami, and Tulsiani, Luca showed that $\exp(-O(\log^2 s))$-biased densities suffices to $.01$-fool size-$s$ DNF formulas. Is it possible that $s^{-O(1)}$-biased densities suffice? (Note: to $\delta$-fool size-$s$ DNF, Luca’s work shows that $s^{-O(\log(1/\delta))}$-biased densities are necessary.)

Following Luca, Gil spoke and raised a rather open-ended problem that arose from some discussions at the symposium. Let $\mathbf{x}_1, \dots, \mathbf{x}_n$ be standard independent normal random variables, and consider circuits over these variables whose gates are: a) linear forms; b) max; c) min. What can be said about the computational complexity of such circuits? Gil hoped that these circuits might be easier to understand than the analogous Boolean circuits.

Next up was Rocco Servedio who presented the problem “Average versus Max Sensitivity for Monotone Functions”.

Johan Håstad spoke next and proposed a problem that is essentially due to Ke Yang from 2004: Fix an unbiased function $f : \{-1,1\}^n \to \{-1,1\}$. Let $\mathbf{x} \sim \{-1,1\}^n$ be uniformly random. Alice knows $f$ but has only partial information about $\mathbf{x}$. Specifically, for each $i \in [n]$, she learns $\mathbf{x}_i$ with probability $p$, and with probability $1-p$ she learns no information. Alice’s task is to predict the value $f(\mathbf{x})$. Assuming $p < 1/2$, is it true that she has the best chance of succeeding when $f$ is the majority function (assume $n$ odd)? Note that for $p > 1/2$, O’Donnell and Wright recently proved that Alice’s best chance of succeeding is when $f$ is a dictator.

The next open problem was from Hamed Hatami. He asks: What is least number $m$ of ${\mathbb F}_2$-quadratic polynomials $q_1, \dots, q_m$ such that the AND function $\{-1,1\}^n \to \{-1,1\}$ is expressible as $\sum_{i=1}^m c_i (-1)^{q_i}$, where the $c_i$’s are real. Hamed knows that $m \geq n$ is necessary, but conjectures that in fact $m$ must be exponentially large in $n$. Even proving $m \geq n^3$, say, seems difficult. Note that if the quadratics must in fact be linear then we know that $m = 2^n$ is necessary and sufficient (this is just from the Fourier expansion); if Hamed’s conjecture is true, it would give a kind of uncertainty principle for quadratic Fourier analysis.

Following Hamed, Shachar described the Polynomial Bogolyubov Conjecture.

Our last open problem was presented by Irit Dinur. She recalled the Ahlswede–Khachatrian Theorem which states that for $k < n/2$, the maximum cardinality of a $t$-intersecting family of subsets of $\binom{[n]}{k}$ is given by one of the following sets: $\{S \subseteq [n], |S| = k : |S \cap [2r + t]| \geq r+t\}$ for $r = 0, 1, 2, \dots$. She also recalled that the proof of this theorem is a very difficulty combinatorial argument. Her open problem is to give a more “analytic” proof of the theorem. Here, one should probably consider the $p$-biased measure version of the problem (in which the family need not consist just of $k$-sets, but is measured with respect to the $p$-biased distribution, $p < 1/2$).

Irit’s main question: Suppose $\mathcal{D}$ is a distribution over $[0,1]$ with mean $p < 1/2$. Let us define $A \subseteq [0,1]^n$ to be “$t$-intersecting” if $\langle x, y \rangle \geq t$ for every $x, y \in A$. (Note: $t$ need not be an integer.) What is the maximal volume of such an $A$ under the product distribution $\mathcal{D}^{\otimes n}$? Her conjecture here is that a maximizing $A$ is of the form $\{x \in [0,1]^n : \langle x, z \rangle \geq \alpha\}$ for some $z \in [0,1]^n$ and $\alpha \in {\mathbb R}$.

Irit also asks about the robustness version of the question: if $A$ is a $t$-intersecting set of close to maximal volume, must it be close to a maximizer?

She also notes that Friedgut gave an analytic (and robust) proof of Ahlswede–Khachatrian for the special case of the $p$-biased distribution on $\{0,1\}^n$, $t \geq 1$, and $p < 1/(t+1)$.

2 comments to Simons Symposium: final open problems

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>