11institutetext: HSE University, Russian Federation
11email<EMAIL_ADDRESS>
# On Separation between the Degree of a Boolean Function and the Block
Sensitivity††thanks: The article was prepared within the framework of the HSE
University Basic Research Program

Nikolay V. Proskurin

###### Abstract

In this paper we study the separation between two complexity measures: the
degree of a Boolean function as a polynomial over the reals and the block
sensitivity. We show that the upper bound on the largest possible separation
between these two measures can be improved from $d^{2}(f)\geq bs(f)$,
established by Tal [19], to $d^{2}(f)\geq(\sqrt{10}-2)bs(f)$. As a corollary,
we show that the similar upper bounds between some other complexity measures
are not tight as well, for instance, we can improve the recent sensitivity
conjecture result by Huang [10] $s^{4}(f)\geq bs(f)$ to
$s^{4}(f)\geq(\sqrt{10}-2)bs(f)$. Our techniques are based on the paper by
Nisan and Szegedy [14] and include more detailed analysis of a symmetrization
polynomial.

In our next result we show the same type of improvement for the separation
between the approximate degree of a Boolean function and the block
sensitivity: we show that $\deg_{1/3}^{2}(f)\geq\sqrt{6/101}bs(f)$ and improve
the previous result by Nisan and Szegedy [14]
$\deg_{1/3}(f)\geq\sqrt{bs(f)/6}$. In addition, we construct an example
showing that the gap between the constants in the lower bound and in the known
upper bound is less than $0.2$.

In our last result we study the properties of a conjectured fully sensitive
function on 10 variables of degree 4, existence of which would lead to
improvement of the biggest known gap between these two measures. We prove that
there is the only univariate polynomial that can be achieved by symmetrization
of such a function by using the combination of interpolation and linear
programming techniques.

###### Keywords:

degree of a Boolean function approximate degree block sensitivity

##  1 Introduction

Let $f$: $\\{0,1\\}^{n}\to\\{0,1\\}$ be a Boolean function. We can represent
$f$ in many ways, for example, as a polynomial over the reals. It is easy to
show that every Boolean function can be uniquely represented by such a
polynomial (see [11, exercise 2.23]), so we can introduce a complexity measure
that is the degree of the polynomial that represents $f$, denoted by $d(f)$.
Another representation of $f$ related to polynomials is the approximating one:
a polynomial is called a $\varepsilon$-approximation of $f$ if for any
$x\in\\{0,1\\}^{n}$ we have $|f(x)-p(x)|\leq\varepsilon$. Such polynomials
make sense for any $0<\varepsilon<\frac{1}{2}$, and it is often assumed that
$\varepsilon=\frac{1}{3}$. By $\deg_{\varepsilon}(f)$ we denote the minimum
degree among the polynomials that $\varepsilon$-approximates $f$.

Exact and approximation degrees are closely related to the model called
decision trees. The main measure in this model is a decision tree complexity
$D(f)$, which is equal to the amount of bits in input we need to ask in order
to give the value of $f$ on such input. Other complexity measures include a
sensitivity $s(f)$ and a block sensitivity $bs(f)$. If we denote

$x^{(R)}=\begin{cases}1-x_{i}&i\in R\\\ x_{i}&i\notin R\end{cases}$

then a local block sensitivity $bs(f,x)$ is the largest amount of disjoint
blocks $R_{1},\ldots,R_{t}$ such that $f(x)\neq f(x^{(R_{i})})$ for every
$i=1,\ldots,t$. A block sensitivity in general is the maximum over the local
block sensitivities for $x\in\\{0,1\\}^{n}$. A local sensitivity and
sensitivity defined similarly with a restriction that all the blocks must be
of size 1. See the [4] for an overview of these and other complexity measures
in the decision tree model.

One of the questions involving various complexity measures is determining the
relations between them. For example, recently Huang resolved [10] the well-
known sensitivity conjecture and established that $s^{4}(f)\geq bs(f)$. As for
polynomials, the first result of this kind was made by Nisan and Szegedy: they
analyzed symmetrizations of Boolean functions and showed that $2d^{2}(f)\geq
bs(f)$ [14]. Later, Tal improved this bound by a constant factor by studying a
function composition, proving that $d^{2}(f)\geq bs(f)$ [19]. However, the
best known example with low degree and high block sensitivity is due to
Kushilevitz [9, Example 6.3.2], in which $bs(f)=n=6^{k}$ while
$d(f)=3^{k}=n^{\log_{6}{3}}\simeq n^{0.61}$. That means there is still a large
gap between the upper and lower bounds in this separation. Our result is the
next constant factor improving:

###### Theorem 1.1

For all Boolean functions $\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$d^{2}(f)\geq(\sqrt{10}-2)bs(f)\simeq 1.16bs(f)$ (1)

As a corollary of this result, we also improve some other relations between
complexity measures, including the Huang’s result: we prove that
$s^{4}(f)\geq(\sqrt{10}-2)bs(f)$.

As for approximating polynomials, Nisan and Szegedy proved that
$\deg_{1/3}(f)\geq\sqrt{bs(f)/6}$ and provided an example (namely, the
$OR_{n}$ function), for which the constrain is tight up to a constant factor.
Later, similar results were archived for this and other Boolean functions [18,
5, 2]. In presented papers, authors were not interested in a constant factor
in bounds. In our result, we improve the constant in the lower bound and prove
that

###### Theorem 1.2

For all Boolean functions $\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$\deg_{1/3}^{2}(f)\geq\sqrt{\frac{6}{101}}bs(f)\simeq 0.24bs(f)$ (2)

We also provide an example of a Boolean function (namely, the $NAE_{n}$) that
can be approximated with a polynomial of degree asymptotically tight to our
bound and with a low constant factor in it; in fact, the difference is less
than $0.2$, which shows that the lower bound is not far from optimal.

Another way to approach the problem of the separation between $d(f)$ and
$bs(f)$ is to provide examples of functions of low degree and high
sensitivity. The first known example was given by Nisan and Szegedy: like in
the Kushilevitz’s function, $f$ is fully sensitive, depends on $n=3^{k}$
variables and $d(f)=2^{k}=n^{\log_{3}{2}}\simeq n^{0.63}$. Both examples
achieved by composing the base function with itself arbitrary amount of times,
and one can show that in the fully sensitive case in such a composition both
$d(f)$ and $bs(f)$ remain the same in terms of $n$. This technique was later
studied by Tal in [19]. In [14] the base polynomial consists of 3 variables
and has the degree of 2, while in the [9, Example 6.3.2] it has 6 variables
and the degree of 3. In both examples $2n=d(d+1)$, so the next natural step is
the fully sensitive $\tilde{f}$ on 10 variables with $d(\tilde{f})=4$.
Existence of such a function would lead to the new best example of the
separation with $bs(\tilde{f})=n$ and $d(\tilde{f})=n^{\log_{10}{4}}\simeq
n^{0.60}$. While we do not provide an example of $\tilde{f}$, we prove that
the only polynomial that can be achieved by symmetrization of it is:

$\tilde{p}(x)=-\frac{x^{4}}{144}+\frac{5x^{3}}{36}-\frac{125x^{2}}{144}+\frac{125x}{72}$
(3)

Our techniques for the lower bounds are based on Nisan and Szegedys’ paper. We
use the same symmetrization approach but with the more detailed analysis of a
symmetrization polynomial: we apply better bounds and study higher order
derivatives. As for the upper bounds, we analyze the Chebyshev polynomials of
the first kind for approximating polynomials and use the combination of
interpolation and linear programming for exact polynomials.

In Section 2 we provide necessary definitions and theorems. In Sections 3, 4
and 5 we prove the lower bound for exact polynomials, the result for
approximating polynomials and the property of the low degree function
$\tilde{f}$ respectively.

##  2 Preliminaries

In this paper we assume that in input of a Boolean function 1 corresponds to
the logical true while 0 corresponds to the logical false. The weight of an
input is the amount of the positive bits in it. We use the notation
$||P||=\sup_{x\in[-1;1]}|P(x)|$ and denote the set of polynomials of degree at
most $d$ by $\mathcal{P}_{d}$.

A symmetrization of a polynomial $p$: $\mathbb{R}^{n}\to\mathbb{R}$ defined as
follows:

$p^{sym}(x)=\frac{1}{n!}\sum_{\pi\in S_{n}}p(\pi(x))$ (4)

$S_{n}$ denotes the group of permutations of size $n$ and $\pi(x)$ denotes the
new input, with bits from $x$ moved according to the permutation $\pi$.

The following lemma allows us to represent $p^{sym}$ as a univariate
polynomial of small degree:

######  Lemma 1 (Symmetrization lemma [13])

If $p$: $\mathbb{R}^{n}\to\mathbb{R}$ is a multilinear polynomial, then there
exists a univariate polynomial $\tilde{p}$: $\mathbb{R}\to\mathbb{R}$ of
degree at most the degree of $p$ such that:

$p^{sym}(x_{1},\ldots,x_{n})=\tilde{p}(x_{1}+\ldots+x_{n}),\quad\forall
x\in\\{0,1\\}^{n}$

Note that the value of $\tilde{p}(k)$ for $k=0,1,\ldots,n$ is equal to the
fraction of inputs such that the weight of $x$ is equal to $k$ and $p(x)=1$.

From the proof of this lemma we can also get the explicit formula for the
$\tilde{p}$:

$\tilde{p}(x)=c_{0}+c_{1}\binom{x}{1}+c_{2}\binom{x}{2}+\ldots+c_{d}\binom{x}{d},\quad
d\leq\deg{p}$ (5)

By definition for the binomial coefficients. put:

$\binom{x}{k}=\frac{x\cdot(x-1)\cdot\ldots\cdot(x-k+1)}{k!}$

The original work of Nisan and Szegedy used the following theorem to bound the
degree of a polynomial:

######  Theorem 2.1 ([7, 16])

Let $p$: $\mathbb{R}\to\mathbb{R}$ be a polynomial such that $b_{1}\leq
p(k)\leq b_{2}$ for every integer $0\leq k\leq n$ and a derivative satisfies
$|p^{\prime}(\eta)|\geq c$ for some real $0\leq\eta\leq n$; then

$\deg(p)\geq\sqrt{\dfrac{nc}{c+b_{2}-b_{1}}}.$

However, it is obvious that $\sqrt{\dfrac{c}{c+b_{2}-b_{1}}}<1$, so any bound
achieved using this theorem would be weaker than Tal’s $d^{2}(f)\geq bs(f)$.
In order to make progress, we are going to use the following theorem by Ehlich
and Zeller, as well as the Markov brothers’ inequality:

######  Theorem 2.2 ([7])

Let $p$: $\mathbb{R}\to\mathbb{R}$ be a polynomial of degree $d$. Suppose
$n\in\mathbb{N}$ satisfies:

  1. 1.

$\rho=\dfrac{d^{2}(d^{2}-1)}{6n^{2}}<1$, and

  2. 2.

$\forall k=0,1,\ldots,n$: $x_{k}=-1+\dfrac{2k}{n}$, $|p(x_{k})|<1$

then $||p||\leq\dfrac{1}{1-\rho}$.

######  Theorem 2.3 (Markov brothers’ inequality)

For any $p\in\mathcal{P}_{d}$ and $k<d$:

$||p^{(k)}||\leq\frac{d^{2}\cdot(d^{2}-1)\cdot\ldots\cdot(d^{2}-k+1)}{1\cdot
3\cdot\ldots\cdot(2k-1)}||p||$ (6)

A Boolean function $f$ is called fully sensitive at 0 iff $f(0)=0$ and
$s(f,0)=n$. The next theorem by Nisan and Szegedy explains why it is enough
for us to focus only on fully sensitive functions.

######  Theorem 2.4 ([14])

For every Boolean function $f$ there exists the fully sensitive at 0 function
$\tilde{f}$ that depends on $bs(f)$ variables and $d(\tilde{f})\leq d(f)$.

The simple proofs of Theorems 1, 2.2 and 2.4 are given in Appendix 0.A. While
the proof of the Markov brothers’ inequality is significantly harder, two
“book-proof”s of it are given in [17].

##  3 Exact Polynomials

In this section we study the separation between the degree of a Boolean
function as an exact polynomial and the block sensitivity. The result
organized as follows. Firstly, we will prove the warm-up result, in which we
introduce a new approach for bounding degree of a polynomial. Secondly, we
will prove a series of lemmas for the main result and prove Theorem 1.1.

###  3.1 Warm-up

In order to show new techniques, first we are going to prove a simpler result,
which, however, is still better than the previously known upper bound for this
separation:

###### Theorem 3.1

For all Boolean functions $\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$d^{2}(f)\geq\sqrt{6/5}bs(f)\simeq 1.09bs(f)$ (7)

First of all, we need to derive a new approach to bound the degree of a
polynomial that would be stronger than Theorem 2.1.

###### Theorem 3.2

Let $p$: $\mathbb{R}\to\mathbb{R}$ be a polynomial of degree $d$ such that:

  1. 1.

$\forall i=0,1,\ldots,n$: $0\leq p(i)\leq 1$, and

  2. 2.

$\sup_{x\in[0;n]}|p^{(k)}(x)|\geq c$.

Then either $d^{2}\geq\sqrt{6}n$ or the ratio $x=\dfrac{d^{2}}{n}$ satisfies
the following inequality:

$\left(1-\frac{x^{2}}{6}\right)\frac{(2k-1)!!}{2^{k-1}}c<x^{k}$ (8)

$(2k-1)!!$ denotes the double factorial:
$(2k-1)!!=(2k-1)\cdot(2k-3)\cdot\ldots\cdot 3\cdot 1$.

###### Proof

Suppose $d^{2}<\sqrt{6}n$, otherwise the first statement holds. In terms of
Theorem 2.2:

$\rho=\frac{d^{2}(d^{2}-1)}{6n^{2}}<\frac{d^{4}}{6n^{2}}<1$ (9)

Let $P(x)$ be defined as follows:

$P(x)=p\left(\frac{n}{2}(x+1)\right)-\frac{1}{2}$

By Theorem 2.2, $||P||\leq\dfrac{1}{2}\cdot\dfrac{1}{1-\rho}$. On the other
hand, $||P^{(k)}||\geq\dfrac{n^{k}}{2^{k}}\cdot c$. Combined with Inequality
2.3, we get

$c\left(\frac{n}{2}\right)^{k}\leq||P^{(k)}||\leq\frac{d^{2}\cdot(d^{2}-1)\cdot\ldots\cdot(d^{2}-k+1)}{1\cdot
3\cdot\ldots\cdot(2k-1)}||P||<\frac{d^{2k}}{(2k-1)!!}\cdot\frac{1}{2(1-\rho)}$
$(1-\rho)\frac{(2k-1)!!}{2^{k-1}}c\leq\left(\frac{d^{2}}{n}\right)^{k}$ (10)

By substituting (9) and $x=\dfrac{d^{2}}{n}$ into (10), we obtain exactly the
inequality (8).

The same approach was used by Beigel [1, lemma 3.2], however, he didn’t
parameterized his result and proved it only for the first derivative. If we
apply his result with a trivial bound $\sup_{x\in[0;n]}|p^{\prime}(x)|\geq 1$,
it follows that $1-\dfrac{x^{2}}{6}<x$ for $x=\dfrac{d^{2}}{n}$. As $x>0$, the
solution is $x\geq\sqrt{15}-3\simeq 0.87$, which is stronger than the original
bound, but weaker than the Tal’s result.

Now we are ready to prove the warm-up result.

######  Proof (Theorem 3.1)

Because of reduction 2.4, we can assume without loss of generality that $f$ is
fully sensitive at 0, and so a polynomial $p$ derived from Lemma 1 satisfies
$p(0)=0$ and $p(1)=1$. Also, it is obvious that if $\rho$ from Theorem 2.2 is
not less than $1$, then $d^{2}\geq\sqrt{6}n>\sqrt{6/5}n$, so we assume that
$\rho<1$.

Suppose $p\in\mathcal{P}_{2}$, i.e. $p(x)=ax^{2}+bx+c$. From the values of
$p(0),\ p(1)$ and $p(2)$ we obtain the following constrains:

  1. 1.

$p(0)=c=0\Rightarrow c=0$.

  2. 2.

$p(1)=a+b+c=1\Rightarrow a+b=1$.

  3. 3.

$p(2)=4a+2b\Rightarrow-2\leq 2a\leq-1$.

As a result, $|p^{\prime\prime}(x)|=|2a|\geq 1$.

In general case, let $q(x)$ be the quadratic polynomial that equals to $p(x)$
at $x\in\\{0,1,2\\}$, and $\tilde{p}(x)=p(x)-q(x)$. From our definition it
follows that $\tilde{p}(0)=\tilde{p}(1)=\tilde{p}(2)=0$, so there exists
$\xi\in[0;2]$: $\tilde{p}^{\prime\prime}(\xi)=0$. Then
$|p^{\prime\prime}(\xi)|=|q^{\prime\prime}(\xi)+\tilde{p}^{\prime\prime}(\xi)|\geq
1$, and as a direct consequence $\sup_{x\in[0;n]}|p^{\prime\prime}(\xi)|\geq
1$. Substituting $c=1$ and $k=2$ in (8), we obtain the following inequality
for $x=\dfrac{d^{2}}{n}$:

$\left(1-\frac{x^{2}}{6}\right)\frac{3}{2}<x^{2}$ (11)

Since $x\geq 0$, we get $x\geq\sqrt{6/5}$ and $d^{2}\geq\sqrt{6/5}n$.

###  3.2 Proof of Theorem 1.1

To increase the constant factor from $\sqrt{6/5}$ to $\sqrt{10}-2$, we should
analyze higher order derivatives. In order to do so, we are going to use
representation (5). We also need to establish a series of lemmas.

###### Lemma 2

Suppose $f$: $\\{0,1\\}^{n}\to\\{0,1\\}$ is fully sensitive at 0 and $n\geq
4$; then for symmetrization polynomial $p$ we have
$\sup_{x\in[0;n]}|p^{\prime\prime\prime}(x)|\geq 1-p(3)$.

###### Lemma 3

$\sum_{k=4}^{\infty}\frac{1}{k2^{k-2}}<\frac{1}{8}$ (12)

The proofs are omitted to Appendix 0.A. With this lemmas we are ready for the
main proof.

######  Proof (Theorem 1.1)

If $n<4$, then the theorem follows from Tal’s bound $d^{2}(f)\geq bs(f)$. As
in Theorem 3.1, we assume that $f$ is fully sensitive at $0$ and $\rho<1$.

It is easy to show that

$\binom{x}{k}^{\prime}\bigg{|}_{x=0}=\frac{(-1)^{k+1}}{k},\quad
k\in\mathbb{N}$

If we combine this with representation (5), we get the formula for the first
derivative of the symmetrization polynomial at $x=0$:

$p^{\prime}(0)=\sum_{k=1}^{d}(-1)^{k+1}\frac{c_{k}}{k}$ (13)

We can bound the first three coefficients:

  1. 1.

$p(1)=c_{1}=1\Rightarrow c_{1}=1$.

  2. 2.

$p(2)=2c_{1}+c_{2}\leq 1\Rightarrow c_{2}\leq-1$.

  3. 3.

$p(3)=3c_{1}+3c_{2}+c_{3}\geq 0\Rightarrow c_{3}\geq p(3)$.

If $p(3)<\dfrac{3}{8}$, then by Lemma 2
$\sup_{x\in[0;n]}|p^{\prime\prime\prime}(x)|>\dfrac{5}{8}$. Substituting
$c=\dfrac{5}{8}$ and $k=3$ in (8), we get the inequality for
$x=\dfrac{d^{2}}{n}$:

$\left(1-\frac{x^{2}}{6}\right)\frac{75}{32}<x^{3}$

Inequality implies that $x>1.2$, which satisfies the statement of the theorem.
In remaining case, we have $c_{3}\geq\dfrac{3}{8}$. Substituting all the
constrains in (13), we obtain:

$p^{\prime}(0)\geq\frac{3}{2}+\frac{1}{8}+\sum_{k=4}^{d}(-1)^{k+1}\frac{c_{k}}{k}$
(14)

Suppose $|c_{k}|<\dfrac{1}{2^{k-2}}$ for $k>3$, then

$p^{\prime}(0)\geq\frac{3}{2}+\frac{1}{8}-\sum_{k=4}^{d}\frac{1}{k2^{k-2}}>\frac{3}{2}+\frac{1}{8}-\sum_{k=4}^{\infty}\frac{1}{k2^{k-2}}>\frac{3}{2}+\frac{1}{8}-\frac{1}{8}=\frac{3}{2}$

Inequality (8) with $c=\dfrac{3}{2}$ and $k=1$ implies
$\left(1-\dfrac{x^{2}}{6}\right)\dfrac{3}{2}\leq x$ for $x=\dfrac{d^{2}}{n}$.
The solution is $x\geq(\sqrt{10}-2)$, which means that
$d^{2}\geq(\sqrt{10}-2)n$.

The only case left to consider is if there exists such $k>3$ that
$|c_{k}|\geq\dfrac{1}{2^{k-2}}$. To deal with it, we first need to show that
$\sup_{x\in[0;n]}|p^{(k)}(x)|\geq c_{k}$. If $d=k$, then the derivative is a
constant and equals to $c_{k}$ because $\binom{x}{k}^{(k)}=1$. In other case,
let $q(x)$ be the polynomial that consists of all the terms from (5) up to one
with the $c_{k}$. Then $\tilde{p}(x)=p(x)-q(x)$ equals to 0 for
$x=0,1,\ldots,k$, so $\exists\xi\in[0;k]$: $\tilde{p}^{(k)}(\xi)=0$ and
$|p^{(k)}(\xi)|=|c_{k}|$.

Now, for $k=4,5$ we obtain the following inequalities from (8):

$\left(1-\frac{x^{2}}{6}\right)\frac{105}{32}\leq x^{4}\quad\Rightarrow\quad
x>1.24>(\sqrt{10}-2)$ $\left(1-\frac{x^{2}}{6}\right)\frac{945}{128}\leq
x^{5}\quad\Rightarrow\quad x>1.3>(\sqrt{10}-2)$

For $k>5$, we need to show that the solution from the inequality would not be
worse than for $k=5$. Notice that every time we increase $k$ in inequality (8)
we multiply the left hand side by $\dfrac{2k+1}{4}>\sqrt{6}$ and the right
hand side by $x$. But if we recall that $\rho<1$, we get $x<\sqrt{6}$, and
thus the inequality becomes tighter. As a result, the statement holds for
$k>5$ as well.

###  3.3 Corollaries

While our improvement may seem insignificant, it shows that the currently
known bound between $d(f)$ and $bs(f)$ is not tight. Next two corollaries
shows that the same holds for some other pairs of complexity measures.

###### Corollary 1

For all Boolean functions $\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$s^{4}(f)\geq(\sqrt{10}-2)bs(f)$ (15)

###### Proof

In the proof of the sensitivity conjecture [10], Huang established the
following bound for $d(f)$:

$s^{2}(f)\geq d(f)$ (16)

Combined with Theorem 1.1, it follows that

$s^{4}(f)\geq d^{2}(f)\geq(\sqrt{10}-2)bs(f)$

###### Corollary 2

For all Boolean functions $\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$d^{3}(f)\geq(\sqrt{10}-2)D(f)$ (17)

###### Proof

Combining Theorem 1.1 with the bound $D(f)\leq bs(f)\cdot d(f)$ from the paper
[12], we get

$d^{3}(f)\geq d(f)\cdot(\sqrt{10}-2)bs(f)\geq(\sqrt{10}-2)D(f)$

##  4 Approximating Polynomials

In this section, we improve the constant factor in the separation between the
degree of an approximating polynomial and the block sensitivity and provide an
example of a polynomial for $NAE_{n}$ function that shows that not only our
bound is asymptotically tight, but the difference between the best known
constant in the lower bound and the constant in our example is relatively
small as well.

###  4.1 Lower bound

Before the proof we need to derive a similar to 3.2 lemma, but this time for
approximating polynomials.

###### Lemma 4

Let $p$: $\mathbb{R}\to\mathbb{R}$ be a polynomial of degree $d$ such that:

  1. 1.

$\forall i=0,1,\ldots,n$: $-\dfrac{1}{3}\leq p(i)\leq\dfrac{4}{3}$, and

  2. 2.

$\sup_{x\in[0;n]}|p^{(k)}(x)|\geq c$.

Then either $d^{2}\geq\sqrt{6}n$ or the ratio $x=\dfrac{d^{2}}{n}$ satisfies
the following inequality:

$\left(1-\frac{x^{2}}{6}\right)\frac{(2k-1)!!}{2^{k}}\cdot\frac{6c}{5}<x^{k}$
(18)

###### Proof

The only difference between this lemma and Theorem 3.2 is the bounds for
$p(k)$, therefore if we define $P(x)$ the same as earlier, we get the weaker
upper bound: $||P||\leq\dfrac{5}{6}\cdot\dfrac{1}{1-\rho}$. The remaining part
of the proof is the same as in 3.2.

######  Proof (Theorem 1.2)

Using reduction 2.4, we can assume that the symmetrization polynomial of $f$
satisfies $-\dfrac{1}{3}\leq p(0)\leq\dfrac{1}{3}$ and $\dfrac{2}{3}\leq
p(1)\leq\dfrac{4}{3}$. As always, we can only consider the case $\rho<1$.
Also, if $n<5$, then the theorem follows from the original bound
$6\deg^{2}_{1/3}(f)\geq bs(f)$.

Suppose that $p\in\mathcal{P}_{3}$. By Lagrange’s interpolation formula for
$x\in\\{0,1,2\\}$ and $x\in\\{0,2,5\\}$:

$p(x)=\frac{(x-1)(x-2)}{2}p(0)+x(2-x)p(1)+\frac{x(x-1)}{2}p(2)$ (19)
$p(x)=\frac{(x-2)(x-5)}{10}p(0)-\frac{x(x-5)}{6}p(2)+\frac{x(x-2)}{15}p(5)$
(20)

From (19) we get $\forall x\quad
p^{\prime\prime}(x)=p(0)-2p(1)+p(2)\leq-1+p(2)$, and if
$p(2)\leq\dfrac{14}{15}$, then $p^{\prime\prime}(x)\leq-\dfrac{1}{15}$.
Otherwise, from (20) we get $\forall x\quad
p(x)=\dfrac{1}{5}p(0)-\dfrac{1}{3}p(2)+\dfrac{2}{15}p(5)\leq\dfrac{11}{45}-\dfrac{1}{3}p(2)\leq-\dfrac{1}{15}$.
If $\deg{p}>3$, we can use the same reduction as in the proof of Theorem 3.1.

Applying (18) with $c=\dfrac{1}{15}$ and $k=2$, we obtain the following
inequality:

$\left(1-\frac{x^{2}}{6}\right)\frac{3}{50}<x^{2}$ (21)

It now follows that $x\geq\sqrt{\dfrac{6}{101}}$ and
$\deg_{1/3}^{2}(f)\geq\sqrt{\dfrac{6}{101}}bs(f)$.

###  4.2 Upper bound

A function $NAE_{n}$: $\\{0,1\\}^{n}\to\\{0,1\\}$ equals to 1 iff
$x\in\\{0^{n},1^{n}\\}$, i.e. all the bits in the input are the same. The next
theorem provides a polynomial that approximates $NAE_{n}$ and gives the upper
bound for $\deg_{1/3}(f)$ in terms of the block sensitivity.

###### Theorem 4.1

Define $d=\lceil\sqrt{c(n-2)}\rceil$ with a constant $c$ satisfying the
following inequality:

$2c+\frac{2}{3}c^{2}-\frac{2c}{3(n-2)}>1$ (22)

Then there exists a polynomial of degree $d$ if $d$ is even and $d+1$
otherwise that is a $\frac{1}{3}$-approximation of $NAE_{n}$.

###### Proof

In our construction, we use the Chebyshev polynomials of the first kind,
defined as $T_{k}(x)=\cos{(k\arccos{x})}$. We need the following properties of
them; proof of property 3 is omitted to Appendix 0.A, and property 4 is [17,
lemma 5.17] for $k=1$ and $k=2$.

  1. 1.

If $k$ is even, then $T_{k}(x)=T_{k}(-x)$.

  2. 2.

$\forall x\in[-1;1]\quad|T_{k}(x)|\leq 1$.

  3. 3.

$T_{k}^{\prime\prime}(\theta)\geq T_{k}^{\prime\prime}(1)$ for $\theta\geq 1$.

  4. 4.

$T_{k}^{\prime}(1)=k^{2}$ and
$T_{k}^{\prime\prime}(1)=\dfrac{k^{4}-k^{2}}{3}$.

By definition, put

$p(x)=1-\dfrac{2T_{k}(\frac{2x-n}{n-2})}{3T_{k}(\frac{n}{n-2})}$ (23)

It is clear from property 1 that $p(0)=p(n)=\dfrac{1}{3}$. If we show that
$T_{k}\left(\dfrac{n}{n-2}\right)\geq 2$, then by property 2 for all $1\leq
k\leq n-1$ we have

$\left|\frac{2T_{k}(\frac{2x-n}{n-2})}{3T_{k}(\frac{n}{n-2})}\right|\leq\frac{2\cdot
1}{3\cdot 2}=\frac{1}{3}\quad\Rightarrow\quad\frac{2}{3}\leq
p(k)\leq\frac{4}{3}$

and $q(x_{1},\ldots,x_{n})=p(n-x_{1}-\ldots-x_{n})$ is indeed the
$\frac{1}{3}$-approximation of $NAE_{n}$.

Substituting $x=1$ in the Taylor series for $T_{k}(\dfrac{n}{n-2})$, we obtain

$\begin{array}[]{c}T_{k}\left(\dfrac{n}{n-2}\right)=T_{k}(1)+\dfrac{2}{n-2}T_{k}^{\prime}(1)+\dfrac{2}{(n-2)^{2}}T_{k}^{\prime\prime}(\theta)\geq\\\
\\\ \geq
T_{k}(1)+\dfrac{2}{n-2}T_{k}^{\prime}(1)+\dfrac{2}{(n-2)^{2}}T_{k}^{\prime\prime}(1)\end{array}$
(24)

The last inequality holds because of property 3. Combining property 4 and
(22), we get:

$\begin{array}[]{c}T_{k}\left(\dfrac{n}{n-2}\right)\geq
1+2c+\dfrac{2}{3(n-2)^{2}}(c^{2}(n-2)^{2}-c(n-2))=\\\ \\\
=1+2c+\dfrac{2}{3}c^{2}-\dfrac{2c}{3(n-2)}\geq 2\end{array}$ (25)

Because the last term in the left hand side of (22) tends to zero as $n$ tends
to infinity, the optimal $c$ tends to the solution of the following
inequality: $2x+\dfrac{2}{3}x^{2}>1$. The solution is
$x>\dfrac{1}{2}(\sqrt{15}-3)\simeq 0.43$, so the difference between $c$ and
the best known lower bound is less than $0.2$, which shows that the bound 1.2
is close to be tight.

##  5 Fully Sensitive Function of Small Degree

The last result of this paper is about an example of a function with low
degree and high block sensitivity. We study properties of conjectured function
$\tilde{f}$ on $10$ variables with $d(\tilde{f})=4$. By applying the same
composition scheme as in the previous examples, we can generalize $\tilde{f}$
for the arbitrary large $n$. While we do not provide an example of
$\tilde{f}$, we prove that if $\tilde{f}$ is fully sensitive at 0, then by
applying Lemma 1 to it, the only univariate polynomial we can get is (3).

We prove this statement in two steps. Firstly, we achieve such a polynomial by
interpolation. Secondly, we prove the uniqueness using the linear programming.

###  5.1 Interpolation

The first part of the proof is to construct polynomial (3). We do this by
establishing the extremal property of all the symmetrizations of degree 4 for
$n\geq 8$.

###### Theorem 5.1

Let $f$: $\\{0,1\\}^{n}\to\\{0,1\\}$ be fully sensitive at 0 and $n\geq 8$;
then for symmetrization polynomial $p$ we have
$\sup_{x\in[0;n]}|p^{(4)}(x)|\geq\frac{1}{6}$. Moreover, the only polynomial
for which inequality is tight is (3).

###### Proof

Using the Lagrange’s interpolation formula for $x\in\\{0,1,2,7,8\\}$ and
$x\in\\{0,1,2,5,7\\}$, we get the following representations:

  1. 1.

$\begin{array}[]{c}\forall x\quad p^{(4)}(x)=-\dfrac{24}{1\cdot 1\cdot 6\cdot
7}+\dfrac{24}{2\cdot 1\cdot 5\cdot 6}p(2)-\dfrac{24}{7\cdot 6\cdot 5\cdot
1}p(7)+\\\ \\\ +\dfrac{24}{8\cdot 7\cdot 6\cdot
1}p(8)=-\dfrac{4}{7}+\dfrac{2}{5}p(2)-\dfrac{4}{35}p(7)+\dfrac{1}{14}p(8)\leq-\dfrac{1}{10}-\dfrac{4}{35}p(7)\end{array}$
(26)

  2. 2.

$\begin{array}[]{c}\forall x\quad p^{(4)}(x)=-\dfrac{24}{1\cdot 1\cdot 4\cdot
6}+\dfrac{24}{2\cdot 1\cdot 3\cdot 5}p(2)-\dfrac{24}{5\cdot 4\cdot 3\cdot
2}p(5)+\\\ \\\ +\dfrac{24}{7\cdot 6\cdot 5\cdot
2}p(7)=-1+\dfrac{4}{5}p(2)-\dfrac{1}{5}p(5)+\dfrac{2}{35}p(7)\leq-\dfrac{1}{5}+\dfrac{2}{35}p(7)\end{array}$
(27)

If $p(7)\leq\dfrac{7}{12}$, then from (26) we get
$p^{(4)}(x)\leq-\dfrac{1}{6}$, otherwise we get the same result from (27).
Inequality is tight iff $p(7)=\dfrac{7}{12},\ p(2)=1,\ p(5)=0$ and $p(8)=1$.
Combined with $p(0)=0$ and $p(1)=1$, we obtain that there is the only
polynomial of degree at most 5 that satisfies all the constrains. By applying
the Lagrange’s interpolation formula, we get polynomial (3).

Note that (3) is indeed a symmetrization polynomial for some function, because
for $k=0,\ldots,10$ the values $p(k)$ represent the fraction of inputs for
corresponding weights (i.e. $\binom{n}{k}\cdot p(k)\in\mathbb{N}_{0}$).

###  5.2 Linear programming

The second part of the proof is to show that (3) is the only symmetrization
polynomial for $n=10$ and $d(f)\leq 4$. This part is done with a linear
programming solver. In our case we are going to use the
scipy.optimize.linprog, the full code for the problem is available at Google
Colab [15].

###### Theorem 5.2

The only symmetrization polynomial for the fully sensitive at 0 function of 10
variables with degree at most 4 is (3).

###### Proof

Suppose $p(x)=c_{1}x+c_{2}x^{2}+c_{3}x^{3}+c_{4}x^{4}$ is the needed
polynomial. We use the necessary (but not sufficient) conditions for $p(x)$ to
create a linear programming task. Namely, we require $p(1)=1,\ \forall
k=2,\ldots,10$: $0\leq p(k)\leq 1$ and some additional constrain for $c_{4}$.
We require a solver to minimize $c_{4}$.

If we add a constrain $c_{4}>0$, solver proves that problem is infeasible.
Without any constrains for $c_{4}$, solver states that the solution is
$-\dfrac{1}{144}$, i.e. the minimum value for $p^{(4)}(x)$ for which solver
can find the solution is $-\dfrac{1}{144}\cdot 24=-\dfrac{1}{6}$. But we know
that the only polynomial for this value is (3), thus we obtain it’s
uniqueness.

##  6 Conclusion

Although we made improvements in relations between some complexity measures,
we strongly suspect that the current results are still not tight. For example,
the choice of points for interpolation in many theorems was not really
justified, so we think that finding a pattern for the choice of interpolation
set is one of the keys for the further improvements. Also, we suspect that by
using Bernstein’s inequality (see [3, theorem 5.1.7]) in Theorem 1.1 with or
instead of the Markov brothers’ inequality for the first derivative one might
improve the result as well.

Another open question occurs if we add further restrictions for the function
$f$, for example, if we want $f$ to be symmetrical. It was proved by von zur
Gathen and Roche that if $n=p-1$ for prime $p$, then $d(f)=n$, and as a
corollary in general $d(f)=n-\mathcal{O}(n^{0.525})$ [8]. It is conjectured
that $d(f)\geq n-3$, but very little progress was made since. For instance,
the result by Cohen and Shpilka [6] states that if $n=p^{2}-1$, then $d(f)\geq
n-\sqrt{n}$.

####  6.0.1 Acknowledgments.

Author would like to thank Vladimir V. Podolskii for the proof idea for
Theorem 3.1.

## References

  * [1] Beigel, R.: Perceptrons, pp, and the polynomial hierarchy. Comput. Complex. 4, 339–349 (1994). https://doi.org/10.1007/BF01263422, https://doi.org/10.1007/BF01263422
  * [2] Bogdanov, A., Mande, N.S., Thaler, J., Williamson, C.: Approximate degree, secret sharing, and concentration phenomena. In: Achlioptas, D., Végh, L.A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA. LIPIcs, vol. 145, pp. 71:1–71:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.71, https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.71
  * [3] Borwein, P., Erdelyi, T.: Polynomials and Polynomial Inequalities. Graduate Texts in Mathematics, Springer New York (1995), https://books.google.ru/books?id=386CC7JnuuwC
  * [4] Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21–43 (2002). https://doi.org/10.1016/S0304-3975(01)00144-X, https://doi.org/10.1016/S0304-3975(01)00144-X
  * [5] Bun, M., Thaler, J.: Dual lower bounds for approximate degree and markov-bernstein inequalities. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science, vol. 7965, pp. 303–314. Springer (2013). https://doi.org/10.1007/978-3-642-39206-1_26, https://doi.org/10.1007/978-3-642-39206-1_26
  * [6] Cohen, G., Shpilka, A.: On the degree of symmetric functions on the boolean cube. Electron. Colloquium Comput. Complex. 17, 39 (2010), http://eccc.hpi-web.de/report/2010/039
  * [7] Ehlich, H., Zeller, K.: Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift pp. 41–44 (1964)
  * [8] von zur Gathen, J., Roche, J.R.: Polynomials with two values. Comb. 17(3), 345–362 (1997). https://doi.org/10.1007/BF01215917, https://doi.org/10.1007/BF01215917
  * [9] Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theory Comput. 4, 1–27 (2011). https://doi.org/10.4086/toc.gs.2011.004, https://doi.org/10.4086/toc.gs.2011.004
  * [10] Huang, H.: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics 190(3), 949–955 (2019), https://www.jstor.org/stable/10.4007/annals.2019.190.3.6
  * [11] Jukna, S.: Boolean Function Complexity - Advances and Frontiers, Algorithms and combinatorics, vol. 27. Springer (2012). https://doi.org/10.1007/978-3-642-24508-4, https://doi.org/10.1007/978-3-642-24508-4
  * [12] Midrijanis, G.: Exact quantum query complexity for total boolean functions. arXiv preprint quant-ph/0403168 (2004)
  * [13] Minsky, M., Papert, S.: Perceptrons - an introduction to computational geometry. MIT Press (1987)
  * [14] Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Comput. Complex. 4, 301–313 (1994). https://doi.org/10.1007/BF01263419, https://doi.org/10.1007/BF01263419
  * [15] Proskurin, N.: Symmetrization linprog. https://colab.research.google.com/drive/1XKJSYLElVxGgZuwHaFy4BdoTN4JIgKXJ?usp=sharing (2020)
  * [16] Rivlin, T.J., Cheney, E.W.: A comparison of uniform approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis 3(2), 311–320 (1966), http://www.jstor.org/stable/2949624
  * [17] Shadrin, A.: Twelve proofs of the markov inequality. Approximation theory: a volume dedicated to Borislav Bojanov pp. 233–298 (2004)
  * [18] Spalek, R.: A dual polynomial for OR. CoRR abs/0803.4516 (2008), http://arxiv.org/abs/0803.4516
  * [19] Tal, A.: Properties and applications of boolean function composition. In: Kleinberg, R.D. (ed.) Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013. pp. 441–454. ACM (2013). https://doi.org/10.1145/2422436.2422485, https://doi.org/10.1145/2422436.2422485

##  Appendix 0.A Omitted Proofs

######  Proof (Lemma 1)

Define $d=\deg{p^{sym}}$ and $P_{k}=\sum_{|S|=k}\prod_{i\in S}x_{i}$ where $S$
are chosen from the subsets of $[n]=\\{1,2,\ldots,n\\}$. Suppose that $S$ is a
monomial in $p$; then by definition symmetrization adds up all the monomials
of size $|S|$ to $p^{sym}$ equal amount of times: in order to get a specific
monomial $S^{\prime}$ one should fix the permutation of variables in
$S^{\prime}$ and in $[n]\setminus S^{\prime}$, thus amount of every monomial
is equal. Therefore, we can rewrite $p^{sym}$ as

$p^{sym}(x)=c_{0}+c_{1}P_{1}(x)+\ldots+c_{d}P_{d}(x)$

Note that we only interested in $x\in\\{0,1\\}^{n}$; therefore, every term in
$P_{k}$ is equal to 1 iff every variable in it is equal to 1. Thus it is
obvious that if $z=x_{1}+x_{2}+\ldots+x_{n}$, then

$p^{sym}(x)=c_{0}+c_{1}\binom{z}{1}+\ldots+c_{d}\binom{z}{d}=\tilde{p}(z)$

$\deg{\tilde{p}}\leq\deg{p}$ because $\deg{p^{sym}}\leq\deg{p}$.

######  Proof (Theorem 2.2)

Define $K=\inf\\{k:||p||\leq 1+k\\}$. From Inequality 2.3 we get

$||p^{\prime\prime}(x)||\leq\frac{d^{2}(d^{2}-1)}{3}(1+K)$ (28)

Let $\xi$ be the point of maximum on $[-1;1]$, i.e. $||p||=|p(\xi)|$. The
cases $\xi=\pm 1$ are trivial because $|p(\xi)|\leq 1$, so we can assume that
$\xi$ is an inner point and $p^{\prime}(\xi)=0$. Also, because $\forall
k=0,1,\ldots,n-1\quad x_{k+1}-x_{k}=\dfrac{2}{n}$ there exists such $k$ that
$\left|x_{k}-\xi\right|\leq\dfrac{1}{n}$. Applying Taylor series for $p(x)$,
we obtain

$p(x_{k})=p(\xi)+(x_{k}-\xi)p^{\prime}(\xi)+\frac{(x_{k}-\xi)^{2}}{2}p^{\prime\prime}(\theta)=p(\xi)+\frac{(x_{k}-\xi)^{2}}{2}p^{\prime\prime}(\theta),\quad\theta\in[-1;1]$

Substituting (28) in the last equality, we get another bound for $||p||$:

$\begin{array}[]{c}||p||=|p(\xi)|=\left|p(x_{k})-\dfrac{(x_{k}-\xi)^{2}}{2}p^{\prime\prime}(\theta)\right|\leq|p(x_{k})|+\left|\dfrac{(x_{k}-\xi)^{2}}{2}p^{\prime\prime}(\theta)\right|\leq\\\
\\\
1+\dfrac{1}{2n^{2}}\cdot\dfrac{d^{2}(d^{2}-1)}{3}(1+K)=1+\rho(1+K)\end{array}$
(29)

By definition $K\leq\rho(1+K)$ and as a corollary $K\leq\dfrac{\rho}{1-\rho}$
and $||p||\leq 1+K\leq\dfrac{1}{1-\rho}$.

######  Proof (Theorem 2.4)

Let $x$ be the input such that $bs(f)=bs(f,x)$, and let
$S_{1},S_{2},\ldots,S_{t}$ be the blocks on which we achieve such block
sensitivity. Without loss of generality we can assume that $f(0)=0$, otherwise
we can introduce the new function $g(x)=1-f(x)$.

Let $\tilde{f}$ be defined as follows

$\tilde{f}(y_{1},\ldots,y_{t})=f(x\oplus y_{1}S_{1}\oplus\ldots\oplus
y_{t}S_{t})$ (30)

i.e. we create a new input for $f$ such that every bit $x_{j}$ is equal to
$x_{j}\oplus y_{i}$ if $x_{j}\in S_{i}$ or $x_{j}$ is left unchanged
otherwise.

$d(\tilde{f})\leq d(f)$ because $\tilde{f}$ is a linear substitution in $f$.
On the other hand, $\tilde{f}$ is fully sensitive at 0 as
$\tilde{f}(0)=f(0)=0$ and $f(e_{j})=f(x^{(S_{i})})=1$. Thus $\tilde{f}$
satisfies the statement as $t=bs(f)$.

######  Proof (Lemma 2)

Suppose that $p\in\mathcal{P}_{3}$. Using the Lagrange’s interpolation formula
for $x\in\\{0,1,3,4\\}$, we get the following representation:

$p(x)=\frac{x(x-3)(x-4)}{6}-\frac{x(x-1)(x-4)}{6}p(3)+\frac{x(x-1)(x-3)}{12}p(4)$
$\forall x\quad p^{\prime\prime\prime}(x)=1-p(3)+\frac{p(4)}{2}\geq 1-p(3)$

In general case, let $q\in\mathcal{P}_{3}$ be equal to $p$ on the same set of
points. Similarly to Theorem 3.1, if $\tilde{p}(x)=p(x)-q(x)$, then
$\exists\xi\in[0;4]$: $\tilde{p}^{\prime\prime\prime}(\xi)=0$ and
$|p^{\prime\prime\prime}(\xi)|\geq 1-p(3)$.

######  Proof (Lemma 3)

The Maclaurin series for the natural logarithm converges for $-1\leq x<1$.
Substituting $x=-\dfrac{1}{2}$, we can calculate and bound our sum:

$\ln(1+x)=\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k}x^{k}$
$\ln{\frac{1}{2}}=\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k}\left(-\frac{1}{2}\right)^{k}=-\sum_{k=1}^{\infty}\frac{1}{k2^{k}}\quad\Rightarrow\quad\sum_{k=1}^{\infty}\frac{1}{k2^{k}}=\ln{2}$
$\sum_{k=4}^{\infty}\frac{1}{k2^{k-2}}=4\sum_{k=4}^{\infty}\frac{1}{k2^{k}}=4\left(\sum_{k=1}^{\infty}\frac{1}{k2^{k}}-\frac{2}{3}\right)=4\left(\ln{2}-\frac{2}{3}\right)<\frac{1}{8}$

######  Proof (Theorem 4.1, property 3)

As $T_{k}(\cos{x})=\cos{kx}$, we can see that all the roots of the Chebyshev
polynomial lie on $[-1;1]$. By the Rolle’s theorem, all the roots of any
derivative of the Chebyshev polynomial also lie on $[-1;1]$. From [17, lemma
5.17] we get that
$T_{k}^{\prime\prime\prime}(1)=\dfrac{k^{2}(k^{2}-1)(k^{2}-2)}{15}>0$, so
$T_{k}^{\prime\prime\prime}(x)>0$ for $x\geq 1$ and
$T_{k}^{\prime\prime}(\theta)\geq T_{k}^{\prime\prime}(1)$ for $\theta\geq 0$.