Open problem collection (Simons Symposium)

Next week the Simons Foundation is hosting a symposium on Analysis of Boolean Functions in the Virgin Islands; Elchanan Mossel, Krzysztof Oleszkiewicz and I are organizing it.

We are currently collecting problems for the Open Problems session on Monday. I am posting a few “classics” below; please feel free to mention your favourite open problems by email/comments. (Also, as usual, please comment on any necessary corrections, either mathematical or historical.) The final compilation of problems will be posted to arXiv; I’ll also update this post as time goes by.

Stay tuned for future pointers to the symposium’s activities.


Correlation Bounds for Polynomials

Statement: Find an explicit (i.e., in $\mathsf{NP}$) function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ such that we have the correlation bound $|\mathop{\bf E}[(-1)^{\langle f({\boldsymbol{x}}), p({\boldsymbol{x}}) \rangle}]| \leq 1/n$ for every ${\mathbb F}_2$-polynomial $p : {\mathbb F}_2^n \to {\mathbb F}_2$ of degree at most $\log_2 n$.

Source: Folklore dating back to [Raz87,Smo87]

Remarks:

  • The problem appears to be open even with correlation bound $1/\sqrt{n}$ replacing $1/n$.
  • Define the $\textrm{mod}_3$ function to be $1$ if and only if the number of $1$’s in its input is congruent to $1$ modulo $3$. Smolensky [Smo87] showed that $\textrm{mod}_3$ has correlation at most $2/3$ with every ${\mathbb F}_2$-polynomial of degree at most $c\sqrt{n}$ (where $c > 0$ is an absolute constant). For related bounds using his techniques, there seems to be a barrier to obtaining correlation $o(1/\sqrt{n})$.
  • Babai, Nisan, and Szegedy [BNS92] implicitly showed a function in $\mathsf{P}$ which has correlation at most $\exp(-n^{\Theta(1)})$ with any ${\mathbb F}_2$-polynomial of degree at most $.99 \log_2 n$; see also [VW08]. Bourgain [Bou05] (see also [GRS05]) showed a similar (slightly worse) result for the $\textrm{mod}_3$ function.


Tomaszewski’s Conjecture

Statement: Let $a \in {\mathbb R}^n$ have $\|a\|_2 = 1$. Then $\mathop{\bf Pr}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[|\langle a, {\boldsymbol{x}} \rangle| \leq 1] \geq 1/2$.

Source: Question attributed to Tomaszewski in [Guy89]

Remarks:

  • The bound of $1/2$ would be sharp in light of $a = (1/\sqrt{2}, 1/\sqrt{2})$.
  • Holzman and Kleitman [HK92] proved the lower bound $3/8$. In fact they proved $\mathop{\bf Pr}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[|\langle a, {\boldsymbol{x}} \rangle| < 1] \geq 3/8$ (assuming $a_i \neq \pm 1$ for all $i$), which is sharp in light of $a = (1/2, 1/2, 1/2, 1/2)$.


Talagrand’s “Convolution with a Biased Coin” Conjecture

Statement: Let $f : \{-1,1\}^n \to {\mathbb R}^{\geq 0}$ have $\mathop{\bf E}[f] = 1$. Fix any $0 < \rho < 1$. Then $\mathop{\bf Pr}[\mathrm{T}_\rho f \geq t] < o(1/t)$.

Source: [Tal89]

Remarks:

  • Talagrand in fact suggests the bound $O(\frac{1}{t\sqrt{\log t}})$.
  • Talagrand offers a 1000 dollar prize for proving this.
  • Even the “special case” when $f$’s domain is Gaussian space is open.


Sensitivity versus Block Sensitivity

Statement: For any $f : \{-1,1\}^n \to \{-1,1\}$ it holds that $\deg(f) \leq \mathrm{poly}(\mathrm{sens}[f])$, where $\mathrm{sens}[f]$ is the (maximum) sensitivity, $\max_{x} |\{i \in [n] : f(x) \neq f(x^{\oplus i})\}|$.

Source: [CFGS88,Sze89a,GL92,NS94]

Remarks:

  • As the title suggests, it is more usual to state this as $\mathrm{bs}[f] \leq \mathrm{poly}(\mathrm{sens}[f])$, where $\mathrm{bs}[f]$ is the “block sensitivity”. However the version with degree is equally old, and in any case the problems are equivalent since it is known that $\mathrm{bs}[f]$ and $\deg(f)$ are polynomially related.
  • The best known gap is quadratic ([CFGS88,GL92]) and it is suggested ([GL92]) that this may be the worst possible.


Gotsman–Linial Conjecture

Statement: Among degree-$k$ polynomial threshold functions $f : \{-1,1\}^n \to \{-1,1\}$, the one with maximal total influence is the symmetric one $f(x) = \mathrm{sgn}(p(x_1 + \cdots + x_n))$, where $p$ is a degree-$k$ univariate polynomial which alternates sign on the $k+1$ values of $x_1 + \cdots + x_n$ closest to $0$.

Source: [GL94]

Remarks:

  • The case $k = 1$ is easy.
  • Slightly weaker version: degree-$k$ PTFs have total influence $O(k) \cdot \sqrt{n}$.
  • Even weaker version: degree-$k$ PTFs have total influence $O_k(1) \cdot \sqrt{n}$.
  • The weaker versions are open even in the case $k = 2$. The $k = 2$ case may be related to the following old conjecture of Holzman: If $g : \{-1,1\}^n \to {\mathbb R}$ has degree $2$ (for $n$ even), then $g$ has at most $\binom{n}{n/2}$ local strict minima.
  • It is known that bounding total influence by $c(k) \cdot \sqrt{n}$ is equivalent to a bounding $\delta$-noise sensitivity by $O(c(k)) \cdot \sqrt{\delta}$.
  • The “Gaussian special case” was solved by Kane [Kan09].
  • The best upper bounds known are $2n^{1-1/2^k}$ and $2^{O(k)} \cdot n^{1-1/O(k)}$ [DHK+10].


Polynomial Freiman–Ruzsa Conjecture (in the ${\mathbb F}_2^n$ setting)

Statement: Suppose $\emptyset \neq A \subseteq {\mathbb F}_2^n$ satisfies $|A + A| \leq C|A|$. Then $A$ can be covered by the union of $\mathrm{poly}(C)$ affine subspaces, each of cardinality at most $|A|$.

Source: Attributed to Marton in [Ruz93]; for the ${\mathbb F}_2^n$ version, see e.g. [Gre05]

Remarks:

  • The following conjecture is known to be equivalent: Suppose $f : {\mathbb F}_2^n \to {\mathbb F}_2^n$ satisfies $\mathop{\bf Pr}_{{\boldsymbol{x}}, \boldsymbol{y}}[f({\boldsymbol{x}}) + f(\boldsymbol{y}) = f({\boldsymbol{x}} + \boldsymbol{y})] \geq \epsilon$, where ${\boldsymbol{x}}$ and $\boldsymbol{y}$ are independent and uniform on ${\mathbb F}_2^n$. Then there exists a linear function $f : {\mathbb F}_2^n \to {\mathbb F}_2^n$ such that $\mathop{\bf Pr}[f({\boldsymbol{x}}) = \ell({\boldsymbol{x}})] \geq \mathrm{poly}(\epsilon)$.
  • The PFR Conjecture is known to follow from the Polynomial Bogolyubov Conjecture [GT09a]: Let $A \subseteq {\mathbb F}_2^n$ have density at least $\alpha$. Then $A+A+A$ contains an affine subspace of codimension $O(\log(1/\alpha))$. One can slightly weaken the Polynomial Bogolyubov Conjecture by replacing $A+A+A$ with $kA$ for an integer $k > 3$. It is known that any such weakening (for fixed finite $k$) is enough to imply the PFR Conjecture.
  • Sanders [San10] has the best result in the direction of these conjectures, showing that if $A \subseteq {\mathbb F}_2^n$ has density at least $\alpha$ then $4A$ contains a subspace of codimension $O(\log^4(1/\alpha))$. This suffices to give the Freiman–Ruzsa Conjecture with $2^{O(\log^4 C)}$ in place of $\mathrm{poly}(C)$.
  • Green and Tao [GT09a] have proved the Polynomial Freiman–Ruzsa Conjecture in the case that $A$ is monotone.


Mansour’s Conjecture

Statement: Let $f : \{-1,1\}^n \to \{-1,1\}$ be computable by a DNF of size $s > 1$ and let $\epsilon \in (0,1/2]$. Then $f$’s Fourier spectrum is $\epsilon$-concentrated on a collection $\mathcal{F}$ with $|\mathcal{F}| \leq s^{O(\log(1/\epsilon))}$.

Source: [Man94]

Remarks:

  • Weaker version: replacing $s^{O(\log(1/\epsilon))}$ by $s^{O_\epsilon(1)}$.
  • The weak version with bound $s^{O(1/\epsilon)}$ is known to follow from the Fourier Entropy–Influence Conjecture.
  • Proved for “almost all” polynomial-size DNF formulas (appropriately defined) by Klivans, Lee, and Wan [KLW10].
  • Mansour [Man95] obtained the upper-bound $(s/\epsilon)^{O(\log \log(s/\epsilon) \log(1/\epsilon))}$.


Bernoulli Conjecture

Statement: Let $T$ be a finite collection of vectors in ${\mathbb R}^n$. Define $b(T) = \mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[\max_{t \in T} \langle t, {\boldsymbol{x}} \rangle]$, and define $g(T)$ to be the same quantity except with ${\boldsymbol{x}} \sim {\mathbb R}^n$ Gaussian. Then there exists a finite collection of vectors $T’$ such that $g(T’) \leq O(b(T))$ and $\forall t \in T\ \exists t’ \in T’\ \|t-t’\|_1 \leq O(b(T))$.

Source: [Tal94a]

Remarks:

  • The quantity $g(T)$ is well-understood in terms of the geometry of $T$, thanks to Talagrand’s majorizing measures theorem.
  • Talagrand offers a 5000 dollar prize for proving this, and a $1000 prize for disproving it.


Fourier Entropy–Influence Conjecture

Statement: There is a universal constant $C$ such that for any $f : \{-1,1\}^n \to \{-1,1\}$ it holds that $\boldsymbol{H}[\widehat{f}^2] \leq C \cdot \mathbf{I}[f]$, where $\boldsymbol{H}[\widehat{f}^2] = \sum_{S} \widehat{f}(S)^2 \log_2\frac{1}{\widehat{f}(S)^2}$ is the spectral entropy and $\mathbf{I}[f]$ is the total influence.

Source: [FK96b]

Remarks:

  • Proved for “almost all” polynomial-size DNF formulas (appropriately defined) by Klivans, Lee, and Wan [KLW10].
  • Proved for symmetric functions and functions computable by read-once decision trees by O’Donnell, Wright, and Zhou [OWZ11].
  • An explicit example showing that $C \geq 60/13$ is necessary is known. (O’Donnell, unpublished.)
  • Weaker version: the “Min-Entropy–Influence Conjecture”, which states that there exists $S$ such that $\widehat{f}(S)^2 \geq 2^{-C \cdot \mathbf{I}[f]}$. This conjecture is strictly stronger than the KKL Theorem, and is implied by the KKL Theorem in the case of monotone functions.


Majority Is Least Stable Conjecture

Statement: Let $f : \{-1,1\}^n \to \{-1,1\}$ be a linear threshold function, $n$ odd. Then for all $\rho \in [0,1]$, $\mathbf{Stab}_\rho[f] \geq \mathbf{Stab}_\rho[\mathrm{Maj}_n]$.

Source: [BKS99]

Remarks:

  • Slightly weaker version: If $f$ is a linear threshold function then $\mathbf{NS}_\delta[f] \leq \frac{2}{\pi} \sqrt{\delta} + o(\sqrt{\delta})$.
  • The best result towards the weaker version is Peres’s Theorem [Per04], which shows that every linear threshold function $f$ satisfies $\mathbf{NS}_\delta[f] \leq \sqrt{\frac{2}{\pi}} \sqrt{\delta} + O(\delta^{3/2})$.
  • By taking $\rho \to 0$, the conjecture has the following consequence, which is also open: Let $f : \{-1,1\}^n \to \{-1,1\}$ be a linear threshold function with $\mathop{\bf E}[f] = 0$. Then $\sum_{i=1}^n \widehat{f}(i)^2 \geq \frac{2}{\pi}$. The best known lower bound here is $\tfrac{1}{2}$, which follows from the Khinchine–Kahane inequality; see [GL94].


Optimality of Majorities for Non-Interactive Correlation Distillation

Statement: Fix $r \in {\mathbb N}$, $n$ odd, and $0 < \epsilon < 1/2$. For $f : \{-1,1\}^n \to \{-1,1\}$, define $P(f) = \mathop{\bf Pr}[f(\boldsymbol{y}^{(1)}) = f(\boldsymbol{y}^{(2)}) = \cdots f(\boldsymbol{y}^{(r)})]$, where ${\boldsymbol{x}} \sim \{-1,1\}^n$ is chosen uniformly and then each $\boldsymbol{y}^{(i)}$ is (independently) an $\epsilon$-noisy copy of ${\boldsymbol{x}}$. Is it true that $P(f)$ is maximized among odd functions $f$ by the Majority function $\mathrm{Maj}_k$ on some odd number of inputs $k$?

Source: [MO05] (originally from 2002)

Remarks:

  • It is possible (e.g., for $r = 10$, $n = 5$, $\epsilon = .26$) for neither the Dictator ($\mathrm{Maj}_1$) nor full Majority ($\mathrm{Maj}_n$) to be maximizing.


Noise Sensitivity of Intersections of Halfspaces

Statement: Let $f : \{-1,1\}^n \to \{-1,1\}$ be the intersection (AND) of $k$ linear threshold functions. Then $\mathbf{NS}_\delta[f] \leq O(\sqrt{\log k}) \cdot \sqrt{\delta}$.

Source: [KOS02]

Remarks:

  • The bound $O(k) \cdot \sqrt{\delta}$ follows easily from Peres’s Theorem and is the best known.
  • The “Gaussian special case” follows easily from the work of Nazarov [Naz03].
  • An upper bound of the form $\mathrm{polylog}(k) \cdot \delta^{\Omega(1)}$ holds if the halfspaces are sufficiently “regular” [HKM10].


Triangle Removal in ${\mathbb F}_2^n$

Statement: Let $A \subseteq {\mathbb F}_2^n$. Suppose that $\epsilon 2^n$ elements must be removed from $A$ in order to make it “triangle-free” (meaning there does not exist $x, y, x+y \in A$). Is it true that $\mathop{\bf Pr}_{{\boldsymbol{x}}, \boldsymbol{y}}[{\boldsymbol{x}}, \boldsymbol{y}, {\boldsymbol{x}}+\boldsymbol{y} \in A] \geq \mathrm{poly}(\epsilon)$, where ${\boldsymbol{x}}$ and $\boldsymbol{y}$ are independent and uniform on ${\mathbb F}_2^n$?

Source: [Gre05a]

Remarks:

  • Green [Gre05a] showed the lower bound $1/(2\!\uparrow\!\uparrow\!\epsilon^{-\Theta(1)})$.
  • Bhattacharyya and Xie [BX10] constructed an $A$ for which the probability is at most roughly $\epsilon^{3.409}$.


Subspaces in Sumsets

Statement: Fix a constant $\alpha > 0$. Let $A \subseteq {\mathbb F}_2^n$ have density at least $\alpha$. Is it true that $A+A$ contains a subspace of codimension $O(\sqrt{n})$?

Source: [Gre05a]

Remarks:

  • The analogous problem for the group $Z_N$ dates back to Bourgain [Bou90].
  • By considering the Hamming ball $A = \{x : |x| \leq n/2 – \Theta(\sqrt{n})\}$, it is easy to show that codimension $O(\sqrt{n})$ cannot be improved. This example is essentially due to Ruzsa [Ruz93], see [Gre05a].
  • The best bounds are due to Sanders [San10a], who shows that $A+A$ must contain a subspace of codimension $\lceil n/(1+ \log_2(\frac{1-\alpha}{1-2\alpha}))\rceil$. Thinking of $\alpha$ as small, this means a subspace of dimension roughly $\frac{\alpha}{\ln 2} \cdot n$. Thinking of $\alpha = 1/2 – \epsilon$ for $\epsilon$ small, this is codimension roughly $n/\log_2(1/\epsilon)$. In the same work Sanders also shows that if $\alpha \geq 1/2 – .001/\sqrt{n}$ then $A+A$ contains a subspace of codimension $1$.


Aaronson–Ambainis Conjecture

Statement: Let $f : \{-1,1\}^n \to [-1,1]$ have degree at most $k$. Then there exists $i \in [n]$ with $\mathbf{Inf}_i[f] \geq (\mathop{\bf Var}[f]/k)^{O(1)}$.

Source: [Aar08,AA11]

Remarks:

  • True for $f : \{-1,1\}^n \to \{-1,1\}$; this follows from a result of O’Donnell, Schramm, Saks, and Servedio [OSSS05].
  • The weaker lower bound $(\mathop{\bf Var}[f]/2^k)^{O(1)}$ follows from a result of Dinur, Kindler, Friedgut, and O’Donnell [DFKO07].


Bhattacharyya–Grigorescu–Shapira Conjecture

Statement: Let $M \in {\mathbb F}_2^{m \times k}$ and $\sigma \in \{0,1\}^k$. Say that $f : {\mathbb F}_2^n \to \{0,1\}$ is $(M,\sigma)$-free if there does not exist $X = (x^{(1)}, \dots, x^{(k)})$ (where each $x^{(j)} \in {\mathbb F}_2^n$ is a row vector) such that $MX = 0$ and $f(x^{(j)}) = \sigma_j$ for all $j \in [k]$. Now fix a (possibly infinite) collection $\{(M^1, \sigma^1), (M^2, \sigma^2), \cdots \}$ and consider the property $\mathcal{P}_n$ of functions $f : {\mathbb F}_2^n \to \{0,1\}$ that $f$ is $(M^i,\sigma^i)$-free for all $i$. Then there is a one-sided error, constant-query property-testing algorithm for $\mathcal{P}_n$.

Source: [BGS10]

Remarks:

  • The conjecture is motivated by a work of Kaufman and Sudan [KS08] which proposes as an open research problem the characterization of testability for linear-invariant properties of functions $f : {\mathbb F}_2^n \to \{0,1\}$. The properties defined in the conjecture are linear-invariant.
  • Every property family $(\mathcal{P}_n)$ defined by $\{(M^1, \sigma^1), (M^2, \sigma^2), \cdots \}$-freeness is subspace-hereditary; i.e., closed under restriction to subspaces. The converse also “essentially” holds. [BGS10].
  • For $M$ of rank one, Green [Gre05a] showed that $(M,1^k)$-freeness is testable. He conjectured this result extends to arbitrary $M$; this was confirmed by Kr\’{a}l’, Serra, and Vena [KSV08] and also Shapira [Sha09]. Austin [Sha09] subsequently conjectured that $(M,\sigma)$-freeness is testable for arbitrary $\sigma$; even this subcase is still open.
  • The conjecture is known to hold when all $M^i$ have rank one [BGS10]. Also, Bhattacharyya, Fischer, and Lovett [BFL12] have proved the conjecture in the setting of ${\mathbb F}_p$ for affine constraints $\{(M^1,\sigma^1), (M^2,\sigma^2), \dots\}$ of “Cauchy–Schwarz complexity” less than $p$.


Symmetric Gaussian Problem

Statement: Fix $0 \leq \rho, \mu, \nu \leq 1$. Suppose $A,B \subseteq {\mathbb R}^n$ have Gaussian measure $\mu$, $\nu$ respectively. Further, suppose $A$ is centrally symmetric: $A = -A$. What is the minimal possible value of $\mathop{\bf Pr}[{\boldsymbol{x}} \in A, \boldsymbol{y} \in B]$, when $({\boldsymbol{x}}, \boldsymbol{y})$ are $\rho$-correlated $n$-dimensional Gaussians?

Source: [CR10]

Remarks:

  • It is equivalent to require both $A = -A$ and $B = -B$.
  • Without the symmetry requirement, the minimum occurs when $A$ and $B$ are opposing halfspaces; this follows from the work of Borell [Bor85].
  • A reasonable conjecture is that the minimum occurs when $A$ is a centered ball and $B$ is the complement of a centered ball.


Standard Simplex Conjecture

Statement: Fix $0 \leq \rho \leq 1$. Then among all partitions of ${\mathbb R}^n$ into $3 \leq q \leq n+1$ parts of equal Gaussian measure, the maximal noise stability at $\rho$ occurs for a “standard simplex partition”. By this it is meant a partition $A_1, \dots, A_q$ satisfying $A_i \supseteq \{x \in {\mathbb R}^n : \langle a_i, x \rangle > \langle a_j, x \rangle\ \forall j \neq i\}$, where $a_1, \dots, a_q \in {\mathbb R}^n$ are unit vectors satisfying $\langle a_i, a_j \rangle = -\frac{1}{q-1}$ for all $i \neq j$. Further, for $-1 \leq \rho \leq 0$ the standard simplex partition minimizes noise stability at $\rho$.

Source: [IM09]

Remarks:

  • Implies the Plurality Is Stablest Conjecture of Khot, Kindler, Mossel, and O’Donnell [KKMO04]; in turn, the Plurality Is Stablest Conjecture implies it for $\rho \geq -\frac{1}{q-1}$.


$k$-wise Independence for PTFs

Statement: Fix $d \in {\mathbb N}$ and $\epsilon \in (0,1)$. Determine the least $k = k(d,\epsilon)$ such that the following holds: If $p : {\mathbb R}^n \to {\mathbb R}$ is any degree-$d$ multivariate polynomial, and $\boldsymbol{X}$ is any ${\mathbb R}^n$-valued random variable with the property that each $\boldsymbol{X}_i$ has the standard Gaussian distribution and each collection $\boldsymbol{X}_{i_1}, \dots, \boldsymbol{X}_{i_k}$ is independent, then $|\mathop{\bf Pr}[p(\boldsymbol{X}) \geq 0] – \mathop{\bf Pr}[p(\boldsymbol{Z}) \geq 0]| \leq \epsilon$, where $\boldsymbol{Z}$ has the standard $n$-dimensional Gaussian distribution.

Source: [DGJ+09]

Remarks:

  • For $d = 1$, Diakonikolas, Gopalan, Jaiswal, Servedio, and Viola [DGJ+09] showed that $k = O(1/\epsilon^2)$ suffices. For $d = 2$, Diakonikolas, Kane, and Nelson [DKN10] showed that $k = O(1/\epsilon^8)$ suffices. For general $d$, Kane [Kan11b] showed that $O_d(1) \cdot \epsilon^{-2^{O(d)}}$ suffices and that $\Omega(d^2/\epsilon^2)$ is necessary.


Tan–Verbin Conjecture

Statement: Fix any $\epsilon > 0$. Then every monotone $f : \{-1,1\}^n \to \{-1,1\}$ is $\epsilon$-close to a $\mathrm{poly}(\deg(f))$-junta.

Source: Elad Verbin and Li-Yang Tan (independently), 2010

Remarks:

  • One can equivalently replace degree by decision-tree depth or maximum sensitivity.


Average versus Max Sensitivity for Monotone Functions

Statement: Let $f : \{-1,1\}^n \to \{-1,1\}$ be monotone. Then $\mathbf{I}[f] < o(\mathrm{sens}[f])$.

Source: Rocco Servedio, Li-Yang Tan, 2010

Remarks:

  • The tightest example known has $\mathbf{I}[f] \approx \mathrm{sens}[f]^{.61}$; this appears in a work of O’Donnell and Servedio [OS08b].


Linear Coefficients versus Total Degree

Statement: Let $f : \{-1,1\}^n \to \{-1,1\}$. Then $\sum_{i=1}^n \widehat{f}(i) \leq \sqrt{\deg(f)}$.

Source: Ryan O’Donnell, Rocco Servedio, Li-Yang Tan, 2010

Remarks:

  • More ambitiously, one could propose the upper bound $k \cdot \binom{k-1}{\frac{k-1}{2}} 2^{1-k}$, where $k = \deg(f)$. This is achieved by the Majority function on $k$ bits.
  • Apparently, no bound better than the trivial $\sum_{i=1}^n \widehat{f}(i) \leq \mathbf{I}[f] \leq \deg(f)$ is known.



Bibliography for the open problems

13 comments to Open problem collection (Simons Symposium)

  • Anonymous

    Can you give a complete citation for [San10]? It isn’t in the bibliography. Thanks!

  • Allison Lewko

    Here’s a question I have thought about that remains open (as far as I know):

    Among balanced symmetric functions $f:\{1,-1\}^n \rightarrow \{-1,1\}$, does the Majority function exactly minimize the influence of a coordinate? (It is relatively easy to show this holds up to a constant.) For non-balanced symmetric functions, we let $p$ denote the probability that a randomly chosen input maps to 1. Then we may ask more generally, does Majority minimize the quantity $\frac{I[f]}{p(1-p)}$ over all symmetric functions, where $I[f]$ denotes the influence? (We have computationally verified this more general conjecture for $n$ up to 25.)

    • Allison, good question. This could be open as far as I know, too. We are going to have another open problems session; I’ll try to ask your problem if there’s time!

    • I have a fairly simple proof that the optimum is obtained for a linear threshold function. The rest of the Conjecture should be fairly easy to verify from this point. There are still some extensions of this problem that can be considered though.

      * Allison mentioned that a useful generalization would be if I[f] were replaced by the probability that given S random coordinates that an adversary changing the values of the input on these coordinates could change the value of f.

      * Someone (I don’t remember who) suggested looking at this problem with other symmetry groups than all of S_n. I feel like this is going to be a lot more complicated in general, but perhaps something can be said. For example, for the cyclic group you have the “cyclic tribes function” which is 1 if some log(n) (cyclically) consecutive coordinates are all 1. This does noticeably better than majority.

  • igor

    Hi Ryan

    Here is a remark regarding the Subspaces in Sumsets problem.
    If we relax the question and ask for a subspace $V$ such that 99% of $V$ is contained in $A+A$, i.e. $\frac{|V \cap (A+A)|}{|V|} \geq 0.99$,
    then one can show that there is a subspace of constant codimension (that depends on $\alpha$ and 0.99) that satisfies this requirement.
    I have not seen this result written anywhere explicitly, but it follows by a little modification of Green’s proof
    http://www.dpmms.cam.ac.uk/~bjg23/restriction_kakeya_phenomena/notes14.ps

    • Right, good point. In fact, I mean to add this to the open problems’ descriptions. Sanders’s 2010 “Quasipolynomial Freiman-Ruzsa” theorem in fact works by showing that if $A$ has density $\alpha$ then $A+A$ contains 99% of a subspace of codimension $O(\log^4(1/\alpha))$. It immediately follows that $4A$ contains all of this subspace, and this gives “Quasipolynomial Bogolyubov”.) One can presumably hope for $A+A$ to contain 99% of a subspace of codimension $O(\log(1/\alpha))$.

  • syz

    In the first question “Correlation Bounds for Polynomials”, it reads “Find an explicit (i.e., in NP) function…”. Maybe I’m missing something simple here, but … why being explicit means being in NP in the statement?

    Also, is in the expectation actually means f(x)+p(x)? (Otherwise, if f(x) and p(x) both take values in {0,1}, what’s the meaning of the inner product here?) Thanks!

    • Regarding your second point: whoops, you’re right. I fixed it.

      Regarding your first question: I clarified a bit. I guess “explicit” can mean whatever the reader wants it to mean, but one semi-traditional formal meaning is “in NP”. In fact, the positive results we have are all for function (families) in P. It’s actually good to be specific here, because if the problem with NP (unexpectedly) has a negative answer, then it is known to follow that NP has quasipolynomial-size circuits. So in fact, it is even reasonable to search for functions in, say, NEXP, that have correlation at most $1/n$ will all $\log_2(n)$-degree polynomials.

  • I don’t know if anyone is looking at this website anymore, but using the theory of diffuse decompositions (as mentioned in my talk), another bound can be proven for Gotsman-Linial. In particular if f is a degree-k polynomial threshold function, then the total influence of f is at most O_{k,c}(1) n^{5/6+c}.

  • I believe I have a counterexample to the Tan-Verbin Conjecture. In particular I have an explicit family of monotone functions given by degree-d decision trees that are epsilon-far (for constant epsilon) for any $k$-junta for $k = \exp(O(\log^2(d)/\log \log(d)))$. I think that this bound can be improved to $\exp(poly(d))$, but need to check the details a little more carefully.

  • Gil Kalai

    Is it Holzman and Kleitmen?

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>