Applied Statistics Unit, Indian Statistical Institute, Kolkata, India
<EMAIL_ADDRESS>Indian Statistical Institute, Kolkata, India
<EMAIL_ADDRESS>Naval Postgraduate School, Monterey, USA
<EMAIL_ADDRESS>Southwest Jiaotong University, Chengdu, China
<EMAIL_ADDRESS>
#  On Boolean Functions with Low Polynomial Degree and Higher Order
Sensitivity

Subhamoy Maitra  Chandra Sekhar Mukherjee  Pantelimon Stanica  Deng Tang

###### Abstract

Boolean functions are important primitives in different domains of cryptology,
complexity and coding theory. In this paper, we connect the tools from
cryptology and complexity theory in the domain of Boolean functions with low
polynomial degree and high sensitivity. It is well known that the polynomial
degree of of a Boolean function and its resiliency are directly connected.
Using this connection we analyze the polynomial degree-sensitivity values
through the lens of resiliency, demonstrating existence and non-existence
results of functions with low polynomial degree and high sensitivity on small
number of variables (upto 10). In this process, borrowing an idea from
complexity theory, we show that one can implement resilient Boolean functions
on a large number of variables with linear size and logarithmic depth.
Finally, we extend the notion of sensitivity to higher order and note that the
existing construction idea of Nisan and Szegedy (1994) can provide only
constant higher order sensitivity when aiming for polynomial degree of
$n-\omega(1)$. In this direction, we present a construction with low
($n-\omega(1)$) polynomial degree and super-constant $\omega(1)$ order
sensitivity exploiting Maiorana-McFarland constructions, that we borrow from
construction of resilient functions. The questions we raise identify novel
combinatorial problems in the domain of Boolean functions.

###### keywords:

Higher Order Sensitivity, Resiliency, Maiorana-McFarland Construction,
Polynomial Degree, Sensitivity, Separation.

##  1 Introduction

Real polynomial degree (${\sf pdeg}(f)$) and sensitivity ($s(f)$) are two
central properties of Boolean functions in complexity theory, and have been
studied extensively over the past three decades. These notions have important
implications in the domain of query complexity [3] (and not only), where
finding functions with lower polynomial degree than sensitivity generates more
candidates for obtaining super-linear separation between two of the query
complexity models, the classical deterministic and exact quantum models. A
detailed study of these properties and the relations can be found in [3].

Determining the maximum possible separation between sensitivity and polynomial
degree is an open problem that has been studied widely. Implicitly, the
problem reduces to finding the separation between the number of variables and
the real polynomial degree in a fully sensitive function (a function $f$ on
$n$ variables with $s(f)=n$). Informally, the sufficient and necessary
condition for obtaining full sensitivity in a function $f$ on $n$ variables is
to have an input point $\mathbf{x}\in\\{0,1\\}^{n}$ such that
$f(\mathbf{x})=\overline{f(\mathbf{x}^{i})},1\leq i\leq n$, where
$\mathbf{x}^{i}$ is obtained by altering the value of the $i$-th bit of
$\mathbf{x}$. Thus, we fix the output corresponding to some $n+1$ input
points, of the total $2^{n}$ input points. Interestingly, this greatly
restricts the real polynomial degree of the function. Without any restriction,
a function that depends on all of its variables can have ${\sf pdeg}(f)$ as
low as $\mathcal{O}(\log n)$. However, one of the seminal papers [11] in the
study of Boolean functions dictate that ${\sf
pdeg}(f)=\Omega\left({s(f)}^{\frac{1}{2}}\right)$. Furthermore, apart from the
famous recursive amplification method (which is also known as the function
composition), there does not exist any known method to obtain functions with
non-constant separation between $s(f)$ and ${\sf pdeg}(f)$. In fact, the
maximum separation known between $s(f)$ and ${\sf pdeg}(f)$ is achieved by
finding a $6$ variable function with $s(f)=6$ and ${\sf pdeg}(f)=3$ (due to
Kushilevitz [10]) and then recursively amplifying it. This results in a
function $f$ on $n=6^{d}$ variables with full sensitivity ($n$) and polynomial
degree of $3^{d}$ so that $s(f)={{\sf pdeg}(f)}^{\log_{3}6}\approx{{\sf
pdeg}(f)}^{1.63}$ [11]. On the other hand, the real polynomial degree is
intrinsically connected to the cryptographically important property of
resiliency. Specifically if a function $f$ on $n$ variables has ${\sf
pdeg}(f)=m$ then the function $g=f\oplus\mathcal{L}_{n}$ is
$(n-m-1)$-resilient, where $\mathcal{L}_{n}$ is the all variable (symmetric)
linear function. In this paper we refer to $g$ and $f$ as each other’s dual.
In this regard, we define the dual sensitivity ($ds(f)$) property, where a
function $g$ has full dual sensitivity if and only if there exists a point
$\mathbf{x}\in\\{0,1\\}^{n}$ such that $g(\mathbf{x})=g(\mathbf{x}^{i}),1\leq
i\leq n$. This results in a one-to-one connection between the ${\sf
pdeg}(f)$-$s(f)$ relationship and resiliency order-$ds(g)$ relationship, where
$g$ is the dual of $f$. We should remark here that the resilient Boolean
functions have received a lot of interest in construction of symmetric ciphers
as evident from [6, 8, 14].

In this paper, we show that the techniques from complexity theory and
cryptology can supplement each other with respect to combinatorial aspects of
Boolean functions which are important in their own interests, and extend the
notion of sensitivity to higher order towards a better understanding how
fixing of outputs with respect to flipping of more than one input bits can
effect the lower bound on the polynomial degree of a function. That is, we use
different properties of resiliency and polynomial degree to obtain results and
constructions that apply to both paradigms of cryptology and complexity
theory.

###  1.1 Contribution and Organization

Our paper is centered around two related concepts. In the first part we
exploit the well known connection between resiliency and polynomial degree.

We observe an one to one connection between “low polynomial degree-high
sensitivity” and “high resiliency-dual sensitivity” of Boolean functions, via
their Fourier spectrum based definitions. We use this connection to search for
separation between $s(f)$ and ${\sf pdeg}(f)$ for functions on all small
number of variables through the resiliency approach. We find new classes of
functions with maximum $s(f)-pdeg(f)$ separation and obtain super-linear
separation between $n$ and ${\sf pdeg}(f)$ for second and third order
sensitive functions. Specifically we find the following which were not known
earlier.

  * •

There exists second order six variable functions with ${\sf pdeg}(f)=3$. That
is the maximum known separation for $n$ and ${\sf pdeg}$ is same for first and
second order sensitivity.

  * •

There does not exist any $7$ variable fully sensitive function with ${\sf
pdeg}(f)=3$.

Further, We analyze the famous recursive amplification (RA) method. We show
that its generalization allow us to obtain additional classes of functions
with super-linear separation between $s(f)$ and ${\sf pdeg}(f)$. Next, using
the RA method we design efficient circuits (linear size and logarithmic depth
(in $n$) for highly resilient functions $(n-o(n))$, improving upon best known
results. We further obtain bounds on cryptographic properties of these
functions, such as nonlinearity and describe different trade-offs.

We use our resiliency based search method to obtain second order sensitive $6$
variable functions with ${\sf pdeg}(f)=3$. Coupled with the modified recursive
amplification method that we propose in Section 3 (Further elaborated in
Theorem B.1 in Appendix B ), this gives us second order functions $f^{u}$ with
$n=6^{u}$ variables and ${\sf pdeg}(f^{u})=n^{\frac{\log 3}{\log 6}}$,
matching the best known bound between $n$ and ${\sf pdeg}(f)$ for first order
sensitivity. This raises the question of whether asymptotic separation between
$n$ and ${\sf pdeg}(f)$ is a strictly decreasing function when plotted against
sensitivity order.

In the second part, we take a deeper look on higher ($k$-th) order
sensitivity. Sensitivity of a function
$f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$, at a point
$\mathbf{x}\in\mathbb{F}_{2}^{n}$, is the number of bits of $\mathbf{x}$ so
that, upon flipping any one of them, the output of the function also flips.
Extending this, a function is called $k$-th order sensitive, if there is a
point $\mathbf{x}$ such that changing any $1\leq i\leq k$ of the input bits
changes the output of the function. This is a much stronger notion than simple
sensitivity, where a fully sensitive function of present literature ($s(f)=n$)
is a first order one. We are interested in understanding the level of
restriction higher order sensitivity (dual sensitivity) has on polynomial
degree (resiliency).

  * •

In this direction we observe for constant sensitivity order, we can design
functions with sub-linear polynomial degree $o(n)$ using the recursive
amplification method. However, even for functions with ${\sf
pdeg}(f)=\mathcal{O}\left(n-o(n)\right)$, we can only have constant
sensitivity order through this method.

  * •

Finally, we show that the Maiorana-McFarland (MM) construction can be used to
show super-constant separation between $n$ and ${\sf pdeg}(f)$ for functions
with super-constant ($\omega(1)$) sensitivity order. We first design a first
order sensitive function with ${\sf pdeg}(f)=n\log n$, which is worse than the
recursive amplification method as mentioned above. However, by concatenating
non-linear symmetric function in one of the half spaces of the MM function, we
obtain the desirable trade-off. We obtain $k$-th order sensitive functions,
with ${\sf pdeg}(f)=n-\frac{\log\left(\frac{n}{2}-k\right)-\log(k)}{k}$. This
gives us functions with $s(f)=\omega(1)$ and ${\sf pdeg}(f)=n-\omega(1)$. For
example, if we set $k=\log\log(n)$, we get $\log\log(n)$-order sensitive
functions with polynomial degree of $\approx n-\frac{\log n}{\log\log n}$.

The paper is organized as follows. In Section 1.2 we recall the definitions of
sensitivity and polynomial degree and the connection of polynomial degree with
resiliency. Then we briefly describe the concept dual sensitivity, followed by
that of higher order sensitivity and higher order dual sensitivity with the
fundamental equivalences. In Section 2 we obtain the search based results on
sensitivity and higher order sensitivity vs. polynomial degree. In Section 3
we study the recursive amplification method and obtain the related results.
Section 4 is dedicated towards finding functions with higher order sensitivity
and lower than $n$ ($n-w(1)$) polynomial degree. We conclude the paper in
Section 5.

###  1.2 Preliminaries

The definitions of resiliency and polynomial degree are based on the Fourier
spectrum of a Boolean function [12]. A function $f$ has polynomial degree $k$
iff its Fourier spectrum values $W_{f}(\mathbf{x})$ are $0$ for all
$\mathbf{x}\in\\{0,1\\}^{n}$ with hamming weight $wt$ of $\mathbf{x}$ being
greater than $k$. A function $f$ is $k$-resilient if and only if its Fourier
spectrum values are $0$ for all $\mathbf{x}:wt(\mathbf{x})\leq k$. We call a
function to be $k$-th order resilient when it is $k$-resilient but not
$k+1$-resilient. Given a function $f$,
$W_{f}(\mathbf{x})=W_{f\oplus\mathcal{L}_{n}}(\bar{\mathbf{x}})$ where
$\mathcal{L}_{n}$ is the linear function on $n$ variables with
$\bar{\mathbf{x}}$ obtained by flipping each bit of
$\bm{\hat{x}}\in\mathbb{F}_{2}^{n}$. These structural arguments gave rise to
the famous result connecting the resiliency order and polynomial degree of
Boolean functions.

######  Theorem 1.1 ([12], page 150).

If a function $g$ is $k$-th order resilient then the function
$f=g\oplus\mathcal{L}_{n}$ will have a polynomial degree equal to $n-k-1$,
where $\mathcal{L}_{n}=\oplus_{i=1}^{n}x_{i}$.

Next, we study the notion of sensitivity and also, that of dual sensitivity,
which we define to better understand the connection between resiliency and
polynomial degree.

###  1.3 Sensitivity

Sensitivity $s(f)$ is one of the most studied properties of Boolean function.
For any $\mathbf{x}\in\mathbb{F}_{2}^{n}$, we let $\mathbf{x}^{i}$ to be
$\mathbf{x}$ with the $i$-th bit of $\mathbf{x}$ flipped (complemented). The
sensitivity of a Boolean function
$f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$ at a point $\mathbf{x}$ can be
defined as $s(f,\mathbf{x})=|i\in[n]:f(\mathbf{x})\neq f(\mathbf{x}^{i})|$,
and the sensitivity of a function is
$s(f)=\max_{\mathbf{x}\in\mathbb{F}_{2}^{n}}s(f,\mathbf{x}).$ It is natural to
consider the situation where we want the function to have the same value even
if multiple input bits of $\mathbf{x}$ are flipped regardless of their
position. In this direction, we define the $k$-th order sensitivity of a
Boolean function.

$k$-th order sensitivity:  For any set $S\subseteq[n]$ and the input point
$\mathbf{x}\in\mathbb{F}_{2}^{n}$ we define $\mathbf{x}^{(S)}$ as the input
point obtained by flipping the $j$-th bit of $\mathbf{x}$ for all $j\in S$.
Sensitivity is defined around the notion of flipping any single component
corresponding to a given input where the output of the function remains
unchanged. In this regard we define $k$-th order sensitivity of a function in
the following manner.

######  Definition 1.2.

We call a function $f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$ $k$-th
order sensitive if there exists $\mathbf{x}\in\mathbb{F}_{2}^{n}$ such that
$f(\mathbf{x})\neq f\left(\mathbf{x}^{(S)}\right),\leavevmode\nobreak\ \forall
S\subseteq[n],\ 1\leq\lvert S\rvert\leq k.$

That is, $f$ is $k$-th order sensitive if there exists an input so that
flipping any $i\leq k$ of the component bits of the input, changes the
function’s output. Thus a first order sensitive function is simply a function
with $s(f)=n$. The main implication of $k$-th order sensitivity is that it
indeed further restricts how low the degree of the real polynomial
corresponding to the function can be. Without any restrictions we know ${\sf
pdeg}(f)$ can be as low as $\log n$ for functions that depend on $n$
variables. If we fix $s(f)=n$ then the polynomial degree is
$\Omega\left(\sqrt{n}\right)$. The paper is centered around obtaining
functions with $\omega(1)$-order sensitivity and $n-\omega(1)$-polynomial
degree.

###  1.4 Dual sensitivity

Given a function $f$ on $n$ variables with polynomial degree $m$, we call the
function $g=f\oplus\mathcal{L}_{n}$, the dual of $f$, which has $n-m-1$
resiliency. The dual sensitivity of a function
$f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$ at a point $\mathbf{x}$ is
defined as $ds(f,\mathbf{x})=\lvert
i\in[n]:f(\mathbf{x})=f(\mathbf{x}^{i})\rvert$. The dual sensitivity of $f$ is
$ds(f)=\max_{\mathbf{x}\in\mathbb{F}_{2}^{n}}ds(f,\mathbf{x}).$ This notion
can be extended to $k$-th order dual sensitivity in the following manner.

######  Definition 1.3.

We say a function $f$ is $k$-th order dual sensitive if there exists
$\mathbf{x}\in\mathbb{F}_{2}^{n}$, such that, for all $j:1\leq j\leq k$ we
have:

  * •

If $j\equiv 0\bmod 2$, then $f(\mathbf{x})\neq
f\left(\mathbf{x}^{(S)}\right),\ \forall S\subseteq[n]\text{ with }\lvert
S\rvert=j$.

  * •

If $j\equiv 1\bmod 2$, then $f(\mathbf{x})=f\left(\mathbf{x}^{(S)}\right),\
\forall S\subseteq[n]\text{ with }\lvert S\rvert=j$.

That is, a function is $k$-th order dual sensitive if there is an input point
such that if we flip the values of any odd number $\leq k$ of input bits then
the function’s output remains unchanged and if we flip any even number $\leq
k$ of input bits then the function’s output gets complemented.

######  Proposition 1.4.

A function $f$ on $n$ variables is $k$-th order sensitive if and only if its
dual $g=f\oplus\mathcal{L}_{n}$ is $k$-th order dual sensitive.

######  Note 1.5.

We use the following notations:

  * •

An $(n,k,p)$-function is a Boolean function of $n$ variables that is $k$-th
order sensitive and has real polynomial degree at most $p$.

  * •

An $[n,k,m]$-function is a Boolean function of $n$ variables that is $k$-th
order dual sensitive and $m$-resilient.

Thus we have the following proposition.

######  Proposition 1.6.

Thus, if $f$ is an $(n,k,p)$-function then $g=f\oplus\mathcal{L}_{n}$ is an
$[n,k,n-p-1]$-function.

Let us now move onto the search based results.

##  2 Search On Small Variables

As we shall observe in Section 3, upon some modification, the recursive
amplification method can be used to obtain $k$-th order sensitive functions
$f^{u}$ on $d^{u}$ variables with polynomial degree of $p^{u}$, starting from
a function $f$ on $d$ variables and ${\sf pdeg}(f)=p$. Here $p$ is called the
base function. Thus results of low ${\sf pdeg}$ of $k$-th order sensitive
functions on small variables directly generate super-linear separations
between $n$ and ${\sf pdeg}$ for $k$-th order sensitive functions.

For example, if we obtain a fully sensitive (first oder sensitive) function on
$7$ variables with ${\sf pdeg}(f)=3$, or a $10$ variable first order sensitive
function with polynomial degree $4$, then it would improve upon the best known
separation between $s(f)$ and ${\sf pdeg}(f)$. In this direction, the
functions on up to $5$ variables can be exhaustively searched to obtain all
existing combinations. However, for functions on $6$ and more variables, an
exhaustive search is not possible given the size of search space ($2^{64}$ for
$n=6$, $2^{128}$ for $n=7$ and so on), and we instead use the properties of
resiliency and dual sensitivity to completely exhaust the case of fully
sensitive functions for $n=6$ and $n=7$ in terms of obtaining all functions
and proving non existence respectively.

###  2.1 $[4,-,0]$-functions:

It can be checked with a simple search that there does not exist any fully
sensitive function on $4$ variables with ${\sf pdeg}(f)=2$. In fact, if that
would have been the case then we could use the recursive amplification method
to obtain a function $f^{u}$ on $4^{u}$ variables with $s(f^{u})=4^{u}$ and
${\sf pdeg}(f^{u})=2^{u}$, which would give us quadratic separation between
sensitivity and polynomial degree, demonstrating a tight lower bound. Thus we
look into the $(4,-,3)$ functions, which are duals of $[4,-,0]$ functions. We
have the following counts.

  * •

There are approximately $3760(\approx 2^{11.87})$ many $[4,1,0]$-functions.

  * •

Only $256(=2^{8})$ of these functions are $[4,2,0]$-functions and there are no
$[4,3,0]$-functions.

###  2.2 $[5,-,1]$-functions:

In the case of $5$ variable functions, the possible polynomial degree is
between $3$ and $4$. As we have already observed the case of $0$-resiliency
($n-1$ polynomial degree in the dual) for $3$ and $4$, we compute the
$1$-resilient functions in this case, and get the following counts:

$\displaystyle\\#\,[5,1,1]\text{-functions}=12304(\approx 2^{13.58}),$
$\displaystyle\\#\,[5,3,1]\text{-functions}$ $\displaystyle=0$
$\displaystyle\\#\,[5,2,1]\text{-functions}=2464(\approx 2^{11.2}),$
$\displaystyle\\#\,[5,4,1]\text{-functions}$ $\displaystyle=0.$

Finally let us look into the case of $6$ variable functions, for which we have
the best base function for first order sensitivity, which is the Kushilevitz
function.

###  2.3 $[6,-,2]$-functions:

There are total $2^{64}$ Boolean functions on $6$ variables, and checking the
resiliency and sensitivity of all possible functions requires computational
resources that is unattainable. We instead use properties of dual sensitivity
and resiliency to obtain all possible $[6,1,2]$-functions by concatenating the
truth tables of two $5$ variable functions. Any $6$ variable function $f$ can
be written as $f(x_{1},\ldots,x_{6})=(1\oplus
x_{6})f_{2}(x_{1},\ldots,x_{5})\oplus x_{6}f_{2}(x_{1},\ldots,x_{5})$ Where
$f_{1}$ and $f_{2}$ are functions on $5$ variables. Then we have the following
constraints on the properties of $f$.

  1. 1.

If $f$ is $2$-resilient then either both $f_{1}$ and $f_{2}$ are $1$-resilient
or both are $2$-resilient [8].

  2. 2.

If $f$ is fully dual sensitive then at least one of $f_{1}$ and $f_{2}$ are
fully dual sensitive. This is easy to see as if neither $f_{1}$ nor $f_{2}$
are dual sensitive then there is no input point for which the whole function
can have full dual sensitivity.

Now we have only $2^{13}$ many $[5,1,1]$-functions and $2^{18}$ many
$[5,0,1]$-functions, which reduces the effective search space to approximately
$2^{33}$ from the naive $2^{64}$. Using these constraints we get the full
characterization of $[6,-,2]$-functions, which was not previously reported.

  * •

We find that there are $33632(\approx 2^{15.03})$ many $[6,1,2]$-functions.
Here it should be noted that the dual of any such function is a
$(6,1,3)$-function. We can use the modified recursive amplification technique
of Theorem B.1 on all such functions to obtain $(6^{u},1,3^{u})$-functions,
which gives us the best known separation between sensitivity and polynomial
degree, same as the function by Kushilevitz [10].

  * •

We also get $192(\approx 2^{7.6})$ many $[6,2,2]$-functions, and this gives us
the maximum super-linear separation between number of variables and real
polynomial degree in second order sensitive functions, which is ${\sf
pdeg}(f)=n^{\frac{\log 3}{\log 6}}$, which is also the currently best known
separation for first order sensitivity.

Furthermore, there is no $[6,>2,2]$-functions.

###  2.4 Nonexistence of $(7,1,3)$-functions and Searching the Rotation
Symmetric Functions

The existence or non-existence of a $(7,1,3)$-function is central to
understanding the maximum separation between $s(f)$ and ${\sf pdeg}(f)$. If
there does exist a $(7,1,3)$-function then we can obtain a
$(7^{u},1,3^{u})$-function using the recursive amplification method, which
gives $s(f)={{\sf pdeg}(f)}^{\frac{\log 7}{\log 3}}$, improving on the best
known result. However the total number of functions on $7$ variables is
$2^{128}$ and therefore checking all functions for this profile through brute
force is not computationally possible. Against this background we use a mixed
integer linear program (MILP) to investigate the existence of such a function.
If $f$ is a $7$ variable Boolean function with $s(f)=7$ and ${\sf pdeg}(f)=3$
iff there is a vector ${\bf x}\in\mathbb{F}_{2}^{7}$ such that $f({\bf
x})\oplus({\bf x}^{i})=1$ for every $1\leq i\leq 7$ and $W_{f}({\bf u})=0$ for
every ${\bf u}\in\mathbb{F}_{2}^{7}$ with $wt({\bf u}\geq 4$. For every ${\bf
x}\in\mathbb{F}_{2}^{7}$. We run the MILP and it returns no solution for all
choice of $\mathbf{x}$. This shows there are no $(7,1,3)$-functions. One can
refer to Appendix A.1 for a formal description of the constraints.

Even with our strategy, it not possible to search for all fully sensitive and
higher order sensitive functions on more than $7$ variables because of the
size of the search space. In this regard we search $8,9$ and $10$ variable
rotation symmetric functions, which is another cryptographically important
class of functions to obtain with fully sensitive (first order sensitive
functions) using least possible polynomial degree (maximum resiliency in the
dual function). Our findings can be found in Appendix A.2. Let us now proceed
towards the recursive amplification method.

##  3 The Recursive Amplification Method

We have noted that fixing the value of a function corresponding to $n+1$ input
points to make a function fully sensitive, will restrict the polynomial degree
to $\Omega({\sqrt{n}})$. The best known results in this paradigm is derived
through the recursive amplification method, which is also the function
composition method. This is a well known technique that is used to obtain
super-linear separation between $n$ and ${\sf pdeg}(f)$ and is also used to
obtain super-linear separation between $s(f)$ and ${\sf pdeg}(f)$. In this
section we use this technique and obtain the following results:

  1. 1.

A slight modification of the recursive amplification method to obtain super-
linear separation between $s(f)$ and ${\sf pdeg}(f)$ by starting from any
candidate base function.

  2. 2.

We build highly resilient functions with good nonlinearity, $\mathcal{O}(n)$
circuit size and $\mathcal{O}(\log n)$ circuit depth.

  3. 3.

We obtain super-linear separation between number of variables($n$) and
polynomial degree (${\sf pdeg}(f)$) for functions with constant order
sensitivity.

Recursive amplification was used to obtain the largest known separation
between sensitivity and polynomial degree of Boolean functions [3], as well as
the first example of separation between exact quantum query complexity and
deterministic query complexity [1], among other separation results. Let $f$ be
a function on $d$ variables $x_{1},x_{2}\ldots x_{d}$ with polynomial degree
$p$. Then the recursive amplification method generates the function $f^{u}$ on
$d^{u}$ variables as:

  1. 1.

$f^{1}=f$.

  2. 2.

$f^{i+1}\left(x_{1},\ldots,x_{d^{i+1}}\right)=f\left(f^{i}\left(x_{1},\ldots,x_{d^{i}}\right),\ldots,f^{i}\left(x_{(d-1)d^{i}+1},\ldots,x_{d^{i+1}}\right)\right)$.

Then for any $f$ we have ${\sf pdeg}(f^{u})=p^{u}$. Thus if the sensitivity
also gets amplified, we could start with any $d$ variable function with and
obtain $f^{u}$ with super-linear $s(f^{u})-{\sf pdeg}(f^{u})$ whenever
$s(f)>{\sf pdeg}(f)$. However, sensitivity is not always amplified in the
similar manner, and $s(f^{u})$ can be arbitrarily low. To this end we propose
a construction so that we can get super-linear separation between $s()$ and
${\sf pdeg}()$ starting from any function. Furthermore the results also follow
for higher-order sensitivity. Let ${\mathbf{y}}^{i}\in\mathbb{F}_{2}^{d^{i}}$
be obtained by concatenating $d$ copies of ${\mathbf{y}}^{i-1}$. Then we
define the amplification method w.r.t a base function $f$ on $d$ variables as
$f^{i}=f\Big{(}f^{i-1}(x_{1},\ldots,x_{d^{i-1}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus
y_{1},\ldots,f^{i-1}(x_{jd^{i-1}+1},\ldots,x_{(j+1)d^{i-1}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus
y_{j},\ldots,f^{i-1}(x_{(d-1)d^{i-1}+1},\ldots,x_{d^{i}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus y_{d}\Big{)}.$. Then $f^{u}$ is a $k$-th order
sensitive function on $n=d^{u}$ variables and ${{\sf pdeg}(f^{u})={\sf
pdeg}(f)}^{u}$, with $k$-th order sensitivity achieved at the input point
${\mathbf{y}}^{u}$. One can refer to Theorem B.1 in Appendix B for the formal
representation and proof.

Now we look into the functions of $4$ variables and then discuss how the
recursive amplification method can be used to obtain highly resilient
functions with good nonlinearity.

###  3.1 Low cost resilient functions with recursive amplification

Let us consider a function $f$ on $d$ variables with ${\sf pdeg}(f)=p<d$,
where $d$ is a constant. Then we can recursively amplify the function to
obtain a function $f^{u}$ on $n=d^{u}$ variables with ${\sf
pdeg}(f^{u})=p^{u}=n^{\frac{\log p}{\log d}}$. Now if we add the all variables
linear function to it we get an $n$ variable function with $n-n^{\frac{\log
p}{\log d}}-1$ resiliency. However, there already exists many methods of
obtaining Boolean functions with high resiliency and other cryptographically
important properties such as high nonlinearity.

Here the advantage of the recursive amplification method is the circuit size
for building such functions. Building efficient low depth circuits for
cryptographically important functions with large number of input variables is
a challenging problem. In this regard the work by Sarkar et al. [15, 2003] is
important. This work shows how to start with an $m$-resilient function on some
$d$ variables and generate an $m+u$-resilient function on $n=d+u$ variables
that requires $\mathcal{O}(u)$ depth, which is effectively $\mathcal{O}(n)$ as
$d$ is constant for any given construction. In fact, this has been the best
known result in this direction for almost two decades in building efficient
circuits for resilient functions on large variables starting from base
functions. Improving on this, we have the following result.

######  Result 1.

Given a function $f$ on $d$ variables with ${\sf pdeg}(f)=p<d$ we can obtain a
function on $g^{u}$ on $n=d^{u}$ variables with resiliency $n-n^{\frac{\log
p}{\log d}}-1$ such that there is a circuit of linear size and logarithmic
depth (in $n$) for it. Here $g^{u}$ is the dual of $f^{u}$ where $f^{u}$ is
the function on $n^{u}$ variables obtained by recursively amplifying $f$.

The proof can be found in Theorem B.3 in the appendix, followed by Figure 1
that gives an example of building a $9$ variable function using $4$ instances
of the circuit $C_{f}$ corresponding to a $3$-variable function $f$. We refer
to Appendix C for elaborate discussion on the nonlinearity lower bounds we
have derived for these highly resilient functions, along with algebraic
degree-resiliency trade-offs. Finally, we show that we can obtain super-linear
separation between $n$ and ${\sf pdeg}(f)$ for functions with any constant
order sensitivity. This raises the interesting problem of understanding the
nature maximum super-linear separation possible between $n$ and ${\sf
pdeg}(f)$ with increasing, constant order sensitivity $k$. Specifically we
have the following result.

######  Result 2.

Given any constant $k$ there exists a $k$-th order sensitive function $f$ on
$n$ variables such that ${\sf pdeg}(f)=n^{\frac{\log k}{\log k+1}}$, if $k$ is
even and ${\sf pdeg}(f)=n^{\frac{\log k+1}{\log k+2}}$, if $k$ is odd.

One may refer to Section C.1 for the detailed formal explanation.

##  4 Higher Order Sensitivity

Until now we have discussed functions with a constant higher order
sensitivity, and have found classes of functions $f$ defined on the number of
variables $n$ for which we could obtain super-linear separation between $n$
and ${\sf pdeg}(f)$ using the recursive amplification method. However, we
cannot obtain any $t(n)$-order sensitive (or dual sensitive) function, where
$t(n)$ is an increasing function on $n$ using any recursive amplification
process, whenever we intend the function to have less than $n$ polynomial
degree.

######  Theorem 4.1.

The general recursive amplification process cannot obtain a function that has
super-constant order of sensitivity where the polynomial degree of less than
the number of variables, where the recursive amplification process is defined
as

  * •

A base function $f^{1}$ on some $d$ variables.

  * •

$f^{k}=f^{1}\Big{(}\hat{f}^{k-1},\ldots,\hat{f}^{k-1}\Big{)}$ where
$\hat{f}^{k-1}\in\\{f^{k-1},\overline{f^{k-1}}\\}$.

######  Proof 4.2.

Let us consider any function $f$ on $d$ variables and $t(n)$-order sensitivity
where $t(n)=\Omega(1)$. Then $f^{n}$ is a function on $d^{n}$ variables and
there exists $n_{0}\in\mathbb{N}$ such that $t(d^{n_{0}})>d$. However it is
easy to see (via induction) that any function built with a base function on
$d$ variables and sensitivity order less than $d$ cannot be $d$-th order
sensitive.

Thus the recursive amplification process does not help us anymore when we
consider $\omega(1)$-order sensitive functions. In this regard we next explore
the class of Maiorana-McFarland (MM) constructions, a heavily studied class
for cryptographic and coding theoretic purposes.

Here, we use it from the perspective of polynomial degree-sensitivity to
obtain results in the domain of functions with non-constant order of
sensitivity. The layout of this section is as follows. We first discuss the
Maiorana-McFarland construction and then obtain separation between $n$ and
${\sf pdeg}(f)$ while making the function first order sensitive (fully
sensitive). We extend this construction while discussing first order
sensitivity only for ease of understanding. We analyze the polynomial
structure of these functions and obtain logarithmic separation between $n$ and
${\sf pdeg}(f)$. Finally we show that this construction can be modified for
super-constant orders of sensitivity (upto $o(\log n)$ ) with only a few
tweaks.

###  4.1 Maiorana-McFarland construction

The Maiorana-McFarland (MM) construction [4] is based on dividing the input
variable space into two parts and attaching different linear functions from
one subspace to each point in the other subspace, defined as follows.

######  Definition 4.3.

A function $f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$ is called an MM
function if it can be expressed as
$f(\mathbf{x},\mathbf{y})=\left(\phi(\mathbf{x})\cdot\mathbf{y}\right)\oplus
g(\mathbf{x})$, where

  * •

$\mathbf{x}\in\mathbb{F}_{2}^{n_{1}}$ , $\mathbf{y}\in\mathbb{F}_{2}^{n_{2}}$
, $n=n_{1}+n_{2};$

  * •

$\phi$ is a mapping of the form
$\phi:\mathbb{F}_{2}^{n_{1}}\rightarrow\mathbb{F}_{2}^{n_{2}};$

  * •

$g:\mathbb{F}_{2}^{n_{1}}\rightarrow\mathbb{F}_{2}$ is an arbitrary Boolean
function defined on the subspace $\mathbb{F}_{2}^{n_{1}}$.

The Boolean functions due to Maiorana-McFarland construction can be visualized
in different ways. We view them as different linear functions defined on
$\mathbf{y}$ attached to activating values in $\mathbf{x}$. Let there be an MM
Boolean function with any arbitrary map
$\phi:\mathbb{F}_{2}^{n_{1}}\rightarrow\mathbb{F}_{2}^{n_{2}}$ and some
Boolean function $g:\mathbb{F}_{2}^{n_{1}}\rightarrow\mathbb{F}_{2}$.
Corresponding to any $\mathbf{a}\in F^{n_{1}}$, the quantity
$\phi(\mathbf{a})\cdot\mathbf{y}$ is essentially the outcome of the linear
equation $\displaystyle\bigoplus_{\phi(\mathbf{a})_{i}=1}\mathbf{y}_{i}$. Thus
$\phi(\mathbf{a})\cdot\mathbf{y}\oplus g(\mathbf{a})$ equals
$\left(\displaystyle\bigoplus_{\phi(\mathbf{a})_{i}=1}y_{i}\right)\oplus
g(\mathbf{a})$ for all $\mathbf{y}$ in $\mathbb{F}_{2}^{n_{2}}$. Let us denote
this function defined on $\mathbb{F}_{2}^{n_{2}}$ as
$Lin_{\phi(\mathbf{a}),g(\mathbf{a})}$. We now describe two real polynomial
structures.

  1. 1.

$\mathcal{P}_{\mathbf{a}}:\mathbb{F}_{2}^{n_{1}}\rightarrow\mathbb{R},\leavevmode\nobreak\
\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}$ is defined as
$\mathcal{P}_{\mathbf{a}}(\mathbf{x})=\left(\prod\limits_{\mathbf{a}_{i}=0}(1-x_{i})\right)\left(\prod\limits_{\mathbf{a}_{i}=1}x_{i}\right)$,
so that $\mathcal{P}_{\mathbf{a}}(\mathbf{x})=1\text{ if
$\mathbf{x}=\mathbf{a}$ and $0$ otherwise }$

  2.   3. 2.

$Lin_{\phi({\mathbf{a}}),g(\mathbf{a})}$ corresponding to each
$\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}$. Any linear function on $\mathbf{y}$ can
be expressed as $\oplus_{b_{i}=1}y_{i}\oplus
c,\mathbf{b}\in\mathbb{F}_{2}^{n_{2}},c\in\mathbb{F}_{2}$. Then the
$\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y})=\frac{1}{2}-\frac{(-1)^{c}}{2}\prod\limits_{b_{i}=1}(1-2y_{i})$.

Then we have the following real polynomial w.r.t to any MM type function.

######  Proposition 4.4.

Given an MM function
$f(\mathbf{x},\mathbf{y})=(\phi(\mathbf{x})\cdot\mathbf{y})\oplus
g(\mathbf{x})$ on $n$ variables with $\mathbf{x}\in\mathbb{F}_{2}^{n_{1}}$ and
$\mathbf{y}\in\mathbb{F}_{2}^{n_{2}}$, the corresponding real polynomial can
be defined as

$p(\mathbf{x},\mathbf{y})=\displaystyle\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\,\mathcal{L}_{(\phi(\mathbf{a}),g(\mathbf{a}))}(\mathbf{y}).$
(1)

Let us now note down a simple result that this polynomial structure entails.

######  Note 4.5.

For any $\mathbf{b}\in\mathbb{F}_{2}^{n_{2}}$ we have
$\mathcal{L}_{\mathbf{b},c}+\mathcal{L}_{\mathbf{b},\overline{c}}=1$ and ${\sf
pdeg}(\mathcal{L}_{\mathbf{b},c})=wt(\mathbf{b})$.

The structure of the rest of this section is as follows. First we describe
some sufficient condition that allows a MM type function to have $s(f)=n$.
Next we obtain a MM type function with $n-1$ polynomial degree and then extend
this technique to obtain a function with ${\sf pdeg}(f)=n-\log n$. Finally we
extend this notion to higher order sensitivity by adding non-linear functions
on $\mathbb{F}_{2}^{n_{2}}$, which is one of the main results of the paper.

We first ensure $s(f)=n$. We add two restriction to a MM type function.

  1.   2. 1.

$\phi(\bm{1}_{n_{1}})=\bm{1}_{n_{2}}$ and $g(\bm{1}_{n_{1}})=0$.

  3. 2.

$wt\left(\phi(\bm{1}_{n_{1}}^{i})\right)\equiv 1\bmod 2$ and
$g(\bm{1}_{n_{1}}^{i})\equiv n_{2}\bmod 2$.

Then for all such functions we have $s(f)=n$. We denote this class of MM
functions as $\mathbb{MM}_{n}$. Refer to the formal presentation in Lemma D.1
in Appendix D.1. Now we describe the construction for the first separation.

###  4.2 First Order Sensitive Functions With Lower Polynomial Degree

First we show a construction for getting ${\sf pdeg}(f)=n-1$.

######  Construction 1.

Let $f\in\mathbb{MM}_{n}$ be an MM function defined on $n=n_{1}+n_{2}$
variables so that $n_{1}\leq n_{2}\leq n_{1}+1$ with $n_{2}\equiv 0\bmod 2$.
If $f$ is defined using $\phi(\bm{1}_{n_{1}-2}00)=\bm{1}_{n_{2}}$,
$g(\mathbf{x})=\prod_{i=1}^{n_{1}-2}x_{i}(1-x_{n-1})(1-{x_{n}})$, the
sensitivity of $f$ is $n$ and the polynomial degree is at most $n-1$. Refer to
Appendix D.2 for the proof, along with examples and a count on the number of
such functions.

Let us now better understand how the polynomial structure of the MM type
functions can be modified so that the modified polynomial still represents a
Boolean function, but with lower polynomial degree.

###  4.3 Interpreting real polynomial terms via the MM construction

We saw in Proposition 4.4 that the real polynomial corresponding to any MM
type function can be expressed as
$p(\mathbf{x},\mathbf{y})=\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\left(\mathcal{L}_{(\phi(\mathbf{a}),g(\mathbf{a}))}(\mathbf{y})\right).$
We know that
$\mathcal{P}_{\mathbf{a}}(\mathbf{x})=\left(\prod_{i:a_{i}=1}x_{i}\right)\left(\prod_{j:a_{j}=0}(1-x_{j})\right)$.

If $\mathbf{z}=(z_{1},\ldots,z_{k})\in\mathbb{F}_{2}^{k}$, it is easy to see
$\sum_{\mathbf{a}\in\mathbb{F}_{2}^{k}}\left(\big{(}\prod_{i:a_{i}=0}z_{i}\big{)}\big{(}\prod_{j:a_{j}=0}(1-z_{j})\big{)}\right)=1.$
Corresponding to a Boolean function defined on $n$ variables
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})$, we define three non-empty mutually
disjoint sets $S_{1},S_{2}$ and $S_{3}$ such that $S_{1}\cup S_{2}\cup
S_{3}=[n]$ with $\lvert S_{i}\rvert=s_{i}$. Let the variables indexed by
elements in $S_{i}$ be denoted as $x_{i_{j}}$ and
$\mathbf{z}\in\mathbb{F}_{2}^{s_{3}}$ be represented as
$(z_{1},z_{2},\ldots,z_{s_{3}})$. Then the real polynomial $\left(\prod_{i\in
S_{1}}x_{i}\right)\left(\prod_{j\in S_{2}}(1-x_{j})\right)$ can be represented
as $\left(\prod_{i\in S_{1}}x_{i}\right)\left(\prod_{j\in
S_{2}}(1-x_{j})\right)\left(\sum_{\mathbf{z}\in\mathbb{F}_{2}^{s_{3}}}\left(\big{(}\prod_{i:z_{i}=0}x_{3_{i}}\big{)}\big{(}\prod_{j:z_{j}=0}(1-x_{3_{j}})\big{)}\right)\right)$
that is, $\sum_{\mathbf{z}\in\mathbb{F}_{2}^{s_{3}}}\left((\prod_{i\in
S_{1}}x_{i})(\prod_{j\in
S_{2}}(1-x_{j}))(\prod_{i:z_{i}=0}x_{3_{i}})(\prod_{j:z_{j}=0}(1-x_{3_{j}}))\right)$.
This implies that corresponding to an MM type function defined on
$n=n_{1}+n_{2}$ variables, the polynomial
$\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y})(\prod_{i=1}^{k_{1}}x_{i})(\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j}))$
can be interpreted as

$\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}-k_{1}-k_{2}}}\left((\prod_{i=1}^{k_{1}}x_{i})(\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j}))(\prod_{a_{i}=1}x_{k_{1}+k_{2}+i})(\prod_{a_{j}=0}(1-x_{k_{1}+k_{2}+j}))\right)\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y}).$

We represent it as
$\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}-k_{1}-k_{2}}}\mathcal{P}_{(\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{a})}(\mathbf{x})\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y}).$
Thus, we get

$\left((\prod_{i=1}^{k_{1}}x_{i})(\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j}))\right)\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y})=\sum_{\mathbf{t}\in\mathbb{F}_{2}^{n_{1}-k_{1}-k_{2}}}\left(\mathcal{P}_{(\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t})}(\mathbf{x})\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y})\right).$
(2)

These considerations imply the following result.

######  Proposition 4.6.

Let $f$ be an MM function
$f(\mathbf{x},\mathbf{y})=\mathbf{x}\cdot\phi(\mathbf{y})+g(\mathbf{x})$ such
that if $\mathbf{x}=\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}$ then
$\phi(\mathbf{x})=0$ and
$g(\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t})=0,\leavevmode\nobreak\
\forall\mathbf{t}\in\mathbb{F}_{2}^{n_{1}-k_{1}-k_{2}}$. Then the polynomial
corresponding to the Boolean function $f$ can be written as
$p(\mathbf{x},\mathbf{y})=\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}},\mathbf{a}\neq\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\left(\mathcal{L}_{(\phi(\mathbf{a}),g(\mathbf{a}))}(\mathbf{y})\right),$
and the polynomial
$p^{\prime}(\mathbf{x},\mathbf{y})=p(\mathbf{x},\mathbf{y})+\left((\prod_{i=1}^{k_{1}}x_{i})(\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j}))\right)\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y})$
can be written as
$p^{\prime}(\mathbf{x},\mathbf{y})=\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\,\mathcal{L}_{(\phi^{\prime}(\mathbf{a}),g^{\prime}(\mathbf{a}))}(\mathbf{y})$,
where

$\displaystyle\phi^{\prime}(\mathbf{x})$
$\displaystyle=\begin{cases}\phi(\mathbf{x})&\text{if
$\mathbf{x}\neq\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}$ for some
$\mathbf{t}$}\\\ b&\text{otherwise,}\end{cases}$

$\displaystyle g^{\prime}(\mathbf{x})$
$\displaystyle=\begin{cases}g(\mathbf{x})&\text{if
$\mathbf{x}\neq\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}$ for some
$\mathbf{t}$}\\\ c&\text{otherwise}\end{cases}$

and this represents another MM type function $f^{\prime}$ which differs from
$f$ only in the points $\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}$.

Using this result we can attempt to obtain an MM type Boolean function with a
pre-decided real polynomial structure. We start with the real polynomial of a
particular MM type function, and then modifying its corresponding polynomial
by adding
$\left((\prod_{i\in_{1}}^{k_{1}}x_{i})(\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j}))\right)\mathcal{L}_{(\mathbf{b},c)}(\mathbf{y}),$
keeping in mind the respective necessary constraints we have discussed in
terms of $\phi$ and $g$. This gives us another function $f^{\prime}$ whose
structure and its properties can be recovered from $f$. Using this
combinatorial approach we next have the following result.

######  Result 3.

There exists a Boolean function $f\in\mathbb{MM}_{n}$ with ${\sf
pdeg}(f)=n-\Theta(\log n)$.

One can refer to Appendix D.3 for the buildup, along with the proof. Finally
we extend our constructions and results for super-constant orders of
sensitivity.

###  4.4 Extending to super-constant higher order sensitivity via the MM
construction

We have so far observed the situation where we have defined a function on $n$
variables in the MM class as
$f(\mathbf{x},\mathbf{y})=\left(\phi(\mathbf{x})\cdot\mathbf{y}\right)\oplus
g(\mathbf{x})$ where $\mathbf{x}\in\mathbb{F}_{2}^{n_{1}}$ and
$\mathbf{y}\in\mathbb{F}_{2}^{n_{2}}$ with $n_{1}+n_{2}=n$. The simplest
interpretation is choosing a linear function in $\mathbf{y}$ (or its
complement depending on $g$) corresponding to each point
$\mathbf{x}\in\mathbb{F}_{2}^{n_{1}}$. We can extend this to nonlinear
functions in $\mathbf{y}$ being fixed with respect to the points in
$\mathbf{y}$, with $g_{\mathbf{a}}$ being the non-linear function on
$\mathbf{y}$ to be evaluated when $\mathbf{x}=\mathbf{a}$. Then the real
polynomial corresponding to the function $f(\mathbf{x},\mathbf{y})$ can be
written as
$p(\mathbf{x},\mathbf{y})=\displaystyle\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\hat{g}_{\mathbf{a}}(\mathbf{y})$
where $\hat{g}_{\mathbf{a}}:\mathbb{F}_{2}^{n_{2}}\rightarrow\mathbb{R}$ is
the real polynomial corresponding to the function $g_{\mathbf{a}}$. Now let us
discuss some sufficient conditions to obtain $k$-th order sensitivity by
choosing the proper $g_{\mathbf{a}}$ functions.

###  4.5 Obtaining $k$-th order sensitivity an reducing polynomial degree:

We start by defining a function in $\mathbb{F}_{2}^{n_{2}}$ that is $k$-th
order sensitive itself. We define this function as ${\sf
sym}_{n_{2}}^{k}:\mathbb{F}_{2}^{n_{2}}\rightarrow\mathbb{F}_{2},k\leq n$. The
algebraic normal form of the function contains all degree $i,1\leq i\leq k$
monomials. For an example ${\sf sym}^{2}_{4}(\mathbf{y})=y_{1}\oplus
y_{2}\oplus y_{3}\oplus y_{4}\oplus y_{1}y_{2}\oplus y_{1}y_{3}\oplus
y_{1}y_{4}\oplus y_{2}y_{3}\oplus y_{2}y_{4}\oplus y_{3}y_{4}$. Next we
observe the sensitivity order of this function.

######  Lemma 4.7.

The function ${\sf sym}^{k}_{m}$ is a function defined on $m$ variables.
$k$-th order sensitive around the all zero input point $\bm{0}_{m}$.

The proof can be found in Section E.1. Next we define an MM type function
$\mathbb{MM}^{k}_{n}$ with nonlinear functions in $\mathbf{y}$, which is
$k$-th order sensitive.

######  Construction 2.

Any function $f:\mathbb{F}_{2}^{n_{1}+n_{2}}\rightarrow\mathbb{F}_{2}$ with
the algebraic normal form $\displaystyle
f(\mathbf{x},\mathbf{y})=\bigoplus_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\left(ac_{\mathbf{a}}(\mathbf{x})\cdot
g_{\mathbf{a}}(\mathbf{y})\right),$ where $g_{\bm{1}_{n_{1}}}={\sf
sym}^{k}_{n_{2}}$ and $g_{\mathbf{a}}=1$ for all
$\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}:n_{1}>wt(\mathbf{a})\geq n_{1}-k$ is
$k$-th order sensitive.

Finally we extend the technique of Section D.3 to obtain non-constant
separation between number of variables and real polynomial degree in functions
with super-constant order of sensitivity.

######  Construction 3.

There exists a $k$-th order sensitive function in $\mathbb{MM}_{n}^{k}$ with
$n-\frac{\log\left(\frac{n}{2}-k\right)-\log{k}}{k}$ real polynomial degree.

The formal proofs of Constructions 2 and 3 can be found in Appendix E.2. To
reflect on the implications of this result, we can have $\log\log n$-order
sensitive functions with ${\sf pdeg}(f)\approx n-\frac{\log n}{\log\log n}$.
In fact as long as $k=o(\log n)$, we have ${\sf pdeg}(f)=n-\omega(1)$. These
results could not be achieved via the recursive amplification constructions.

##  5 Conclusion

In this paper we have studied the interplay of resiliency and polynomial with
respect to sensitivity, and have also extend the notion of sensitivity to
higher order sensitivity. In this direction based on properties of resilient
functions, we have obtained new classes of $6$-variable first order sensitive
functions with ${\sf pdeg}(f)=3$, while also obtaining the same result for
second order sensitivity. Which indicates that the function of minimum
polynomial degree vs. sensitivity order and may not be a strictly increasing
functions.

Next we have studied the recursive amplification method and have designed
slight modifications that allow us to start with base function, removing the
restrictions of the simple function composition method. Furthermore, we use
the resiliency-polynomial degree connection to design efficient circuits with
linear size and logarithmic depth to realize highly-resilient ($n-o(n)$)
functions. Our result improves on the best result known in this domain.

Finally we observe that for constant orders of sensitivity, we can have
functions with $o(n)$ polynomial degree using the recursive amplification
method. Against this backdrop we take the MM constructions and first obtain
first order sensitive function with ${\sf pdeg}(f)=n-\Theta(\log n)$. Then we
modify the MM construction with nonlinear function concatenation, and obtain
functions with $n-\omega(1)$ polynomial degree and $\omega(1)$ order
sensitivity. Specifically, we show construction of $k$-th order sensitive
function with ${\sf
pdeg}(f)=n-\frac{\log\left(\frac{n}{2}-k\right)-\log{k}}{k}$. Our results
enrich the domain of cryptographically important Boolean functions as long as
lay down important combinatorial problems that should further enhance our
understanding of real polynomial degree of Boolean functions.

## References

  * [1] A. Ambainis, Superlinear advantage for exact quantum algorithms, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (STOC’13), pp. 891–900, 2013.
  * [2] A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs, Separations in Query Complexity Based on Pointer Functions, J. ACM 64:5 (2017), Art. 32, 24 pp.
  * [3] H. Buhrman and R. De Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288:1 (2002), 21–43.
  * [4] J. F. Dillon, Elementary Hadamard Difference sets, Ph.D. Dissertation, Univ. of Maryland (1974).
  * [5] E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proc. AMS 124:10 (1996), 2293–3002.
  * [6] S. Kavut, S. Maitra, and M. D. Yucel, Search for Boolean Functions With Excellent Profiles in the Rotation Symmetric Class, IEEE Transactions on Information Theory, vol. 53, no. 5, pp. 1743-1751, May 2007, doi: 10.1109/TIT.2007.894696.
  * [7] A. Klivans, R. O’Donnell, and R. Servedio, Learning intersections and thresholds of half-spaces, J. Computer and System Sciences 68:4 (2004), 808–840.
  * [8] S. Maitra and P. Sarkar, Highly Nonlinear Resilient Functions Optimizing Siegenthaler’s Inequality Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_13
  * [9] Y. Mansour, Learning Boolean functions via the Fourier transform, Theoretical Advances in Neural Computation and Learning (V. Roychowdhury, K.-Y. Siu, A. Orlitsky, eds.), chapter 11, pp. 391–424, Kluwer Academic Publishers, 1994.
  * [10] N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity 4 (1994), 301–313.
  * [11] N. Nisan and A. Wigderson, On rank vs. communication complexity, Combinatorica 15 (1995), 557–565.
  * [12] R. O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.
  * [13] R. O’Donnell, J. Wright and Y. Zhou, The Fourier entropy–influence conjecture for certain classes of Boolean functions,  in: Proc. of Automata, Languages and Programming – 38th International Colloquium, 2011, pp. 330–341.
  * [14] P. Sarkar and S. Maitra, Construction of Nonlinear Boolean Functions with Important Cryptographic Properties, Advances in Cryptology - EUROCRYPT 2000, LNCS 1807, Springer-Verlag, pp. 485–506 (2000).
  * [15] P. Sarkar and S. Maitra, Efficient implementation of cryptographically useful “large” Boolean functions, IEEE Transactions on Computers 52:4 (2003), 410–417.

##  Appendix A Notes on Search Based Results

###  A.1 Nonexistence of $7$ variable fully sensitive function with Polynomial
Degree Value of $3$

We know that, for any $n$-variable Boolean function $f$, $W_{f}(\mathbf{u})=0$
for every $\mathbf{u}\in\mathbb{F}_{2}^{n}$ with $wt(\mathbf{u})\geq n-m$ if
and only if $pdeg(f)\leq n-m-1$. Thus, $f$ is an $n$-variable Boolean function
with full sensitivity and polynomial degree $k$ if and only if $f\oplus 1$ is
an $n$-variable Boolean function with full sensitivity and polynomial degree
$k$. Therefore, if there are $7$-variable Boolean functions with sensitivity
$7$ and polynomial degree $3$, there exist a $7$-variable Boolean function $f$
with sensitivity $7$, polynomial degree $3$, and a point
$\mathbf{x}\in\mathbb{F}_{2}^{7}$ such that $f(\mathbf{x})=0$ and
$f(\mathbf{x}\oplus e_{i})=1$ for all $1\leq i\leq 7$ where $e_{i}$’s are
pairwise distinct vectors with Hamming weight $1$. Assume that
$f(\overline{i})=y_{i}$, where $\overline{i}$ is the binary expansion of $i$,
and $y_{i^{\prime}}=0$ when $\overline{i^{\prime}}=\mathbf{x}$ and
$y_{i_{1}}=y_{i_{2}}=\ldots={y_{8}}=1$ when $e_{j}=\overline{i_{j}}$, then we
can search if there exist such functions with sensitivity $7$ and polynomial
degree $3$.

$\displaystyle\begin{array}[]{llll}\text{Minimize}&y_{1}&\\\ \text{subject
to}&&\\\
&\sum_{i=1}^{128}(1-2y_{i})(-1)^{\mathbf{u}\cdot\overline{i}}=0&wt(\mathbf{u})\geq
4\\\ &y_{i}\in\\{0,1\\}&1\leq i\leq 128\\\ &y_{i^{\prime}}=0&\\\
&y_{i_{1}}=y_{i_{2}}=\ldots={y_{8}}=1&\end{array}.$

With the help of Gurobi, we checked for every
$\mathbf{x}\in\mathbb{F}_{2}^{7}$ and received a negative outcome in all
cases, concluding that there is no $7$ variable fully sensitive function with
${\sf pdeg}(f)=3$.

###  A.2 Rotation symmetric function for up to $10$ variables

First we check the rotation symmetric functions on $7$ variables to obtain
functions of third order sensitivity and then study rotation symmetric
functions on $ns>7$ variables. We thus obtain the following results:

  * •

There exists $12$ many $[7,1,3]$-functions (respectively $(7,5,3)$-functions).
Recursively amplifying this function gives us a $(7^{u},5^{u},3)$-function, an
instance of ${\sf pdeg}(f)=n^{\frac{\log 7}{\log 5}}$. This is the best
separation we are able to find for third order sensitive functions. It will be
interesting to observe if one can obtain better separation in this case.

  * •

There exists only $12$ functions in the rotation symmetric class that are
$[8,1,3]$-functions and none are $[8,2,3]$-functions. There cannot exist any
$[8,\ell,4]$-function, where $\ell>0$.

  * •

We also find $29$ many $[9,1,4]$ functions rotation symmetric functions, out
of which $27$ are also $[9,2,4]$-functions. Furthermore, there cannot exist
any $[9,\ell,5]$-function, where $\ell>0$. Here one should note that one can
also obtain $[9,1,4]$ and $[9,2,4]$-functions by recursively amplifying a
$(3,1,2)$ or a $(3,2,2)$-function respectively and then taking its dual, and
these were the only known $(9,1,4)$-functions before now. However, we obtain
$[9,1,4]$-rotation symmetric functions with a nonlinearity of $224$, where as
the nonlinearity of the functions obtained through recursive amplification is
$192$. Thus, we obtain previously unknown $(9,1,4)$-functions. The advantage
of using the recursive amplification process is its efficient circuit size and
depth.

  * •

There does not exist any $[10,1,5]$-rotation symmetric function. It should be
noted that if we can obtain a $[10,1,5]$-function (provided such a function
exists) then that would improve on the best known separation between
sensitivity and polynomial degree. This is because we can then get a
$(10,1,4)$-function and then recursively amplify the function using the
modified amplification process described in Theorem B.1 to get a
$(10^{u},1,4^{u})$-function, thus giving $s(f)=\left({\sf
pdeg}(f)\right)^{\frac{\log 10}{\log 4}}$ and this would be an improvement on
the best known result. Furthermore we took all $(9,1,4)$-functions that we
constructed and used the reverse construction [15] where we concatenate the
reverse of the truth table of an even resilient function to itself to get a
function with one more variable and one more resiliency, but this construction
only gave us $(10,0,5)$-function and the sensitivity was not maintained.

This concludes the study of sensitivity-polynomial degree (and higher order
sensitivity-polynomial degree) study of functions on up to $10$ variables.

##  Appendix B Results in Section 3

######  Theorem B.1.

Let $f$ be a $k$-th order sensitive function on $d$ variables with ${\sf
pdeg}(f_{1})=p$ and $\mathbf{y}=(y_{1},y_{2},\ldots,y_{d})$ being the input
with respect to which the function exhibits $k$-th order sensitivity. We
define the function $f^{u}$ on $d^{u}$ variables such that:

  1. 1.

${\mathbf{y}}^{1}=\mathbf{y}$

  2. 2.

${\mathbf{y}}^{i}\in\mathbb{F}_{2}^{d^{i}}$ is obtained by concatenating $d$
copies of ${\mathbf{y}}^{i-1}$.

  3. 3.

$f^{1}=f$

  4. 4.

$f^{i}=f\Big{(}f^{i-1}(x_{1},\ldots,x_{d^{i-1}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus
y_{1},\ldots,f^{i-1}(x_{jd^{i-1}+1},\ldots,x_{(j+1)d^{i-1}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus
y_{j},\ldots,f^{i-1}(x_{(d-1)d^{i-1}+1},\ldots,x_{d^{i}})\oplus
f^{i-1}(\mathbf{y}^{i-1})\oplus y_{d}\Big{)}.$

Then $f^{u}$ is a $k$-th order sensitive function on $n=d^{u}$ variables and
${\sf pdeg}(f)=p^{u}$ with $k$-th order sensitivity achieved at the input
point ${\mathbf{y}}^{u}$.

######  Proof B.2.

Here we call the function $f$ as the base function. Let us denote by
$[\mathbf{x}]_{k}$ any input point that can be obtained by flipping at least
$1$ and at most $k$ variables of $\mathbf{x}\in\mathbb{F}_{2}^{n}$. Thus if a
function $f$ is $k$-th order sensitive at the point $\mathbf{y}$ then
$f([\mathbf{y}]_{k})=\overline{f(\mathbf{y})}$ by definition. We now prove the
result using induction on $u$. The result holds for $u=1$ by definition.
Assume the result holds for $u-1$ and we need to show that the function
$f^{u}$ has $k$-th order sensitivity at $\mathbf{y}^{u}$. The value of the
function at $\mathbf{y}^{u}$ is

$\displaystyle f^{u}(\mathbf{y}^{u})=$ $\displaystyle
f\Big{(}f^{u-1}(\mathbf{y}^{u-1})\oplus f^{u-1}(\mathbf{y}^{u-1})\oplus
y_{1},\ldots,f^{u-1}(\mathbf{y}^{u-1})\oplus f^{u-1}(\mathbf{y}^{u-1})\oplus
y_{d}\Big{)}$ $\displaystyle=$ $\displaystyle f(\mathbf{y}).$

Let us now select any $i\leq k$ variables whose value we wish to flip
resulting in an input point of the form ${[\mathbf{y}^{u}]}_{k}$. We define
the $d$ tuple $S=(s_{1},s_{2},\ldots,s_{d})$ where $s_{i}$ denotes the number
of bits to be flipped between $x_{(i-1)d^{u-1}+1}$ and $x_{id^{u-1}}$. Thus
$0\leq s_{i}\leq k,\leavevmode\nobreak\ \forall i$. If $s_{i}=0$ then

$\displaystyle f^{u-1}(x_{id^{u-1}+1},\ldots,x_{(i+1)d^{u-1}})\oplus
f^{u-1}(\mathbf{y}^{u-1})\oplus a_{i}$
$\displaystyle=f^{u-1}(\mathbf{y}^{u-1})\oplus f^{n-1}(\mathbf{y}^{u-1})\oplus
a_{i}=a_{i}.$

If $1\leq s_{i}\leq k$ then

$\displaystyle f^{u-1}(x_{id^{u-1}+1},\ldots,x_{(i+1)d^{u-1}})\oplus
f^{u-1}(\mathbf{y}^{u-1})\oplus a_{i}$
$\displaystyle=f^{u-1}([\mathbf{y}^{u-1}]_{k})\oplus f^{u-1}(y^{u-1})\oplus
a_{i}=\overline{a_{i}}.$

The number of nonzero values in $S$ are at most $k$, which would change at
most $k$ of the $d$ points $y_{i}$ in the base function’s input to
$\overline{y_{i}}$ and result in an input to $f$ of the form of $f([y]_{k})$.
Thus for the function $f^{u}$ we have
$f^{u}([\mathbf{y}^{u}]_{k})=f([\mathbf{y}]_{k})=\overline{f(\mathbf{y})}=\overline{f^{u}(\mathbf{y}^{u})}$.

The polynomial degree result holds from the basic definition of recursive
amplification as ${\sf pdeg}(f)={\sf pdeg}(\overline{f})$ and this completes
the proof.

######  Theorem B.3.

Given a function $f$ on $d$ variables with ${\sf pdeg}(f)=p<d$ we can obtain a
function on $g^{u}$ on $n=d^{u}$ variables with resiliency $n-n^{\frac{\log
p}{\log d}}-1$ such that there is a circuit of linear size and logarithmic
depth (in $n$) for it.
Here $g^{u}$ is the dual of $f^{u}$ where $f^{u}$ is the function on $n^{u}$
variables obtained by recursively amplifying $f$.

######  Proof B.4.

We first define $f^{u}$ as the function obtained recursively amplifying the
function $f$, $u$ times, which gives us a function on $d^{u}$ variables with
${\sf pdeg}(f^{u})=n^{\frac{\log p}{\log d}}$. Let us assume the circuit
corresponding to the base function on $d$ variables consists of some $c_{d}$
gates and has a depth of $t_{d}$. This circuit takes in $d$ input variable
bits and outputs a single bit. Then the circuit corresponding to $f^{u}$ can
be built using the circuits for $f$ in a layered manner in the following way.

  * •

In the first layer there are total $d^{u-1}$ circuits each taking in $d$
variables each as input bits.

  * •

In the $i$-th layer there $d^{u-i-1}$ circuits each taking as input $d$ of the
$d^{u-i}$ output bits from the previous layer.

  * •

The final layer contains a single circuit, whose output is the output of the
final function.

Then the total number of circuit instances of $f$ to be used is
$\sum_{i=0}^{u-1}d^{i}=\frac{d^{u}-1}{u-1}$ and the gate count is
$c_{d}\times\frac{d^{u}-1}{u-1}=\mathcal{O}(d^{u})=\mathcal{O}(n)$. Moreover,
the depth of this circuit is $u\times t_{d}$ as the circuit for $f$ is set up
in $u$ layers, which gives as a circuit for $f^{u}$ with
$\mathcal{O}(\log_{d}n)$ depth.

Now if we XOR the parity of all the input bits to this output we obtain a
$n-n^{\frac{\log p}{\log d}}-1$ function $g^{u}$ via the resiliency-polynomial
degree connection. The parity of the input bits can be simply obtained in
parallel using $n$ gates and $\log n$ depth, which gives us the result.

Figure 1: Example of a circuit corresponding to recursive amplification.

##  Appendix C Cryptographic Properties of The Highly Resilient Functions

### Other Properties:

Having discussed the efficiency of this method, let us now look into the
nonlinearity of such functions, which is another very important cryptographic
property. We consider the following examples:

  * •

Recursively amplifying a $(3,1,2)$-variable function $f_{3}$ to get a $9$
variable function
$f_{9}(\mathbf{x})=f_{3}\big{(}f_{3}(x_{1},x_{2},x_{3})\oplus
a_{1},f_{3}(x_{4},x_{5},x_{6})\oplus a_{2},f_{3}(x_{7},x_{8},x_{9})\oplus
a_{3}\big{)},\leavevmode\nobreak\ a_{i}\in\\{0,1\\}$ and then adding the all
variable linear function to obtain $g_{9}$, which is $4$ resilient,
irrespective of the choice of $a_{i}$. However, depending on the choice of
$a_{i}$, the nonlinearity can either be $96$ or $192$. Here the circuit for
$f_{3}$ needs $5$ XOR gates and $3$ AND gates and thus the circuit for $f_{9}$
only requires $20$ XOR gates and $12$ AND gates, and we can obtain $g_{9}$ by
adding the all variable parity function, which requires a further $9$ XOR
gates, which makes the total gate count to be only $41$.

  * •

Recursively amplifying a $4$ variable function $f_{4}$ to get a $16$ variable
function $f_{16}$ and then adding the all variable linear function to obtain
$g_{16}$. Here we obtain $16$ variable $11$-resilient functions with
nonlinearity as high as $24576=2^{15}-2^{13}$ where the best possible
nonlinearity for $16$ variable functions is $2^{15}-2^{7}$ (bent functions).

  * •

We also find $(6,1,3)$-functions in Section 2.3 that require $24$ AND gates
and $21$ XOR gates to compute. We can then get a $36$ variable $26$ resilient
fully dual sensitive function with only $168$ AND gates and $147$ XOR gates.

Let us now look into some results on non trivial lower bounds on the
nonlinearity of functions based on the recursive amplification method. Here it
should be noted that the algebraic degree of the function $g^{u}$ is upper
bounded by the real polynomial degree of $f^{u}$, which is $n^{\frac{{\sf
pdeg}(f)}{d}}$.

Let $f$ be a Boolean function on $s$ variables and $g_{1},g_{2},\ldots,g_{s}$
be $s$ Boolean functions on $u$ variables. We now define a $us$-variable
Boolean function $\hat{f}$ by

$\hat{f}\left(x_{1},\ldots,x_{us}\right)=f\left(g_{1}(x_{1},\ldots,x_{u}),g_{2}(x_{u+1},\ldots,x_{2u}),\ldots,g_{s}(x_{us-u+1},\ldots,x_{us})\right).$
(4)

######  Theorem C.1.

Let $\hat{f}$ be the function defined in (4), then for any ${\bf w}=({\bf
w}_{1},\ldots,{\bf w}_{s})\in\mathbb{F}_{2}^{us}$ (where ${\bf
w}_{i}\in\mathbb{F}_{2}^{u}$ for any $1\leq i\leq s$), we have

$\displaystyle W_{\hat{f}}({\bf w})$ $\displaystyle=$ $\displaystyle
2^{-s}\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}\left(W_{f}({\bf
v})\prod_{i=1}^{s}W_{v_{i}g_{i}}({\bf w}_{i})\right),$

where ${\bf v}=(v_{1},v_{2},\ldots,v_{s})\in\mathbb{F}_{2}^{s}$.

######  Proof C.2.

We denote by ${\bf x}$ the vector $(x_{1},\ldots,x_{us})$ and ${\bf x}_{i}$
the vector $(x_{ui-u+1},\ldots,x_{ui})$ for any $1\leq i\leq s$. Then we have
${\bf x}=({\bf x}_{1},{\bf x}_{2},\ldots,{\bf x}_{s})$ and $\hat{f}$ can be
rewritten as $\hat{f}\left({\bf x}\right)=f\left(g_{1}({\bf x}_{1}),g_{2}({\bf
x}_{2}),\ldots,g_{s}({\bf x}_{s})\right)$. For any ${\bf
x}\in\mathbb{F}_{2}^{us}$, we define ${\bf g}=(g_{1}({\bf x}_{1}),g_{2}({\bf
x}_{2}),\ldots,g_{s}({\bf x}_{s}))\in\mathbb{F}_{2}^{s}$. Then for any ${\bf
g}\in\mathbb{F}_{2}^{s}$, we have

$\displaystyle\sum_{{\bf y}\in\mathbb{F}_{2}^{s}}\sum_{{\bf
v}\in\mathbb{F}_{2}^{s}}(-1)^{{\bf v}\cdot({\bf y}+{\bf g})}=2^{s},$ (5)

since $\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}(-1)^{{\bf z}\cdot{\bf v}}$ equals 0
if ${\bf z}\neq{\bf 0}$ and equals $2^{s}$ if ${\bf z}={\bf 0}$. By the
definition of the Walsh transform, for any ${\bf w}=({\bf w}_{1},{\bf
w}_{2},\ldots,{\bf w}_{s})\in\mathbb{F}_{2}^{us}$ we have

$\displaystyle W_{\hat{f}}({\bf w})$ $\displaystyle=$ $\displaystyle\sum_{{\bf
x}\in\mathbb{F}_{2}^{us}}(-1)^{\hat{f}({\bf x})\oplus{\bf w}\cdot{\bf x}}$
$\displaystyle=$ $\displaystyle\sum_{{\bf
x}\in\mathbb{F}_{2}^{us}}(-1)^{f({\bf g})\oplus{\bf w}\cdot{\bf x}}$
$\displaystyle=$ $\displaystyle 2^{-s}\sum_{{\bf
x}\in\mathbb{F}_{2}^{us}}(-1)^{f({\bf y})\oplus{\bf w}\cdot{\bf x}}\sum_{{\bf
y}\in\mathbb{F}_{2}^{s}}\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}(-1)^{{\bf
v}\cdot({\bf y}\oplus{\bf g})}\leavevmode\nobreak\ \leavevmode\nobreak\
(\text{by}\leavevmode\nobreak\ \eqref{eq:linearfun})$ $\displaystyle=$
$\displaystyle 2^{-s}\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}\sum_{{\bf
y}\in\mathbb{F}_{2}^{s}}\sum_{{\bf x}\in\mathbb{F}_{2}^{us}}(-1)^{f({\bf
y})\oplus{\bf v}\cdot{\bf y}\oplus{\bf v}\cdot{\bf g}\oplus{\bf w}\cdot{\bf
x}}$ $\displaystyle=$ $\displaystyle 2^{-s}\sum_{{\bf
v}\in\mathbb{F}_{2}^{s}}\left[\left(\sum_{{\bf
y}\in\mathbb{F}_{2}^{s}}(-1)^{f({\bf y})\oplus{\bf v}\cdot{\bf
y}}\right)\left(\sum_{{\bf x}\in\mathbb{F}_{2}^{us}}(-1)^{{\bf v}\cdot{\bf
g}\oplus{\bf w}\cdot{\bf x}}\right)\right]$ $\displaystyle=$ $\displaystyle
2^{-s}\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}\left(W_{f}({\bf v})\sum_{{\bf
x}_{1},{\bf x}_{2},\ldots,{\bf
x}_{s}\in\mathbb{F}_{2}^{u}}(-1)^{\bigoplus_{i=1}^{s}v_{i}g({\bf
x}_{i})\oplus\bigoplus_{i=1}^{s}{\bf w}_{i}\cdot{\bf x}_{i}}\right)$
$\displaystyle=$ $\displaystyle 2^{-s}\sum_{{\bf
v}\in\mathbb{F}_{2}^{s}}\left(W_{f}({\bf v})\prod_{i=1}^{s}W_{v_{i}g_{i}}({\bf
w}_{i})\right).$

######  Theorem C.3.

Let $\hat{f}$ be the function defined in (4) by taking
$g_{1},g_{2},\ldots,g_{k}\in\mathbb{F}_{2}^{k}$ to be balanced functions. Then
for any ${\bf w}=({\bf w}_{1},{\bf w}_{2},\ldots,{\bf
w}_{s})\in\mathbb{F}_{2}^{ks}$ (where ${\bf w}_{i}\in\mathbb{F}_{2}^{k}$ for
any $1\leq i\leq s$), we have

$\displaystyle W_{\hat{f}}({\bf w})$ $\displaystyle=$ $\displaystyle
2^{-s}W_{f}({\bf
v}^{\prime})\prod_{i=1}^{s}\left(\frac{1+(-1)^{v_{i}^{\prime}}}{2}\cdot
2^{k}+\frac{1-(-1)^{v_{i}^{\prime}}}{2}\cdot W_{g_{i}}({\bf w}_{i})\right),$

where ${\bf
v}^{\prime}=(v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{s}^{\prime})\in\mathbb{F}_{2}^{s}$
with $v_{i}^{\prime}=1$ if and only if ${\bf w}_{i}\neq{\bf 0}_{k}$.
Furthermore, we have

$NL(\hat{f})\geq 2^{ks-1}-2^{ks-
k-s-1}\bigg{(}2^{s}-2NL(f)\bigg{)}\left(2^{k}-2\min_{1\leq i\leq
s}\\{NL(g_{i})\\}\right),$

where $NL$ denotes the nonlinearity.

######  Proof C.4.

Note that the value of the Walsh transform at any nonzero point of a constant
function is equal to null. Thus, for any $1\leq i\leq s$, we have $W_{0}({\bf
w}_{i})=0$ if ${\bf w}_{i}\neq{\bf 0}_{k}$. As $g_{i}$’s are balanced, we have
$W_{g_{i}}({\bf 0}_{k})=0$ for any $1\leq i\leq s$. So we have
$\prod_{i=1}^{s}W_{v_{i}g_{i}}({\bf w}_{i})=0$ if $v_{i}\neq v_{i}^{\prime}$.
Then by Theorem C.1 we have

$\displaystyle W_{\hat{f}}({\bf w})$ $\displaystyle=$ $\displaystyle
2^{-s}\sum_{{\bf v}\in\mathbb{F}_{2}^{s}}\left(W_{f}({\bf
v})\prod_{i=1}^{s}W_{v_{i}g_{i}}({\bf w}_{i})\right)$ $\displaystyle=$
$\displaystyle 2^{-s}W_{f}({\bf
v^{\prime}})\prod_{i=1}^{s}W_{v_{i}^{\prime}g_{i}}({\bf w}_{i}).$

Then our first assertion comes from the fact $W_{v_{i}^{\prime}g_{i}}({\bf
w}_{i})$ equals $2^{k}$ if $v_{i}^{\prime}=0$ and $W_{g_{i}}({\bf w}_{i})$ if
$v_{i}^{\prime}=1$. Note that $|W_{g_{i}}({\bf w}_{i})|\leq\max_{{\bf
w}_{i}^{\prime}\in\mathbb{F}_{2}^{k}}\\{|W_{g_{i}}({\bf
w}_{i}^{\prime})|\\}\leq 2^{k}$ for any $1\leq i\leq s$. Then we have
$|\prod_{i=1}^{s}W_{v_{i}g_{i}}({\bf w}_{i})|\leq 2^{ks-k}\cdot\max_{1\leq
i\leq s,{\bf w}_{i}^{\prime}\in\mathbb{F}_{2}^{k}}\\{|W_{g_{i}}({\bf
w}_{i}^{\prime})|\\}$ by setting the Hamming weight of ${\bf v^{\prime}}$ to
be $1$. Then we can obtain that the nonlinearity of $\hat{f}$ is at least
$2^{ks-1}-2^{ks-k-s-1}\max_{{\bf u}\in\mathbb{F}_{2}^{s}}\\{|W_{f}({\bf
u})|\\}\cdot\max_{1\leq i\leq s,{\bf
w}_{i}^{\prime}\in\mathbb{F}_{2}^{k}}\\{|W_{g_{i}}({\bf w}_{i}^{\prime})|\\}$,
which gives our second assertion. This finishes the proof.

######  Lemma C.5.

Let $f$ be an $n$-variables function and $\hat{f}$ be an $n^{2}$-variable
function defined as
$\hat{f}(x_{1},\ldots,x_{n^{2}})=f\left(f(x_{1},\ldots,x_{n})+a_{1},\ldots,f(x_{n^{2}-n+1},\ldots,x_{n^{2}})+a_{n}\right)$,
where $a_{i}$’s belong to $\mathbb{F}_{2}$. Then the nonlinearity of $\hat{f}$
is at least $2^{n^{2}-n+1}NL(f)-2^{n^{2}-2n+1}\left(NL(f)\right)^{2}$.
Moreover, if $f$ is $m$ resilient, then $\hat{f}$ is $(m+1)^{2}-1$ resilient;
if $w_{f}({\bf w})=0$ for any ${\bf w}$ with Hamming weight no less than
$m^{\prime}$, then $f$ is $n^{2}-(m^{\prime}-1)^{2}-1$ resilient.

######  Proof C.6.

The lower bound on nonlinearity of $\hat{f}$ directly follows from Theorem
C.3. By observing the value of $W_{f}({\bf
v^{\prime}})\prod_{i=1}^{s}W_{v_{i}^{\prime}g_{i}}({\bf w}_{i})$ in the proof
of Theorem C.3, then we can easily obtain the rest assertions. This completes
the proof.

######  Corollary C.7.

Let $f$ be an $n$-variables Boolean function and $f_{i}$ ($i\geq 2$) be the
function defined above. Then we have $NL(f^{i})\geq
2^{n^{i}-n^{i-1}}NL(f^{i-1})+2^{n^{i}-n}NL(f)-2^{n^{i}-n^{i-1}-n+1}NL(f^{i-1})NL(f)$
with $NL(f^{1})=NL(f).$

However, we can also have an algebraic degree-resiliency trade off in this
construction if we use two kinds of base functions on $d$ variables, one with
algebraic degree (and thus polynomial degree) of $d$ and the other having
lower polynomial degree, and we can add these functions in different stages of
the recursion to obtain functions with various resiliency and algebraic degree
values. Thus we have two problems that we propose for further attention as
they are beyond the scope of our current discussion:

  1. 1.

How much can we increase the nonlinearity in $f^{u}$ when the functions used
in recursion are of the form $f$ or $\overline{f}$, where $f$ is the base
function defined on some $d$ variables?

  2. 2.

How good cryptographic profiles can we obtain using this method and using
multiple functions on $d$ variables throughout the recursion process?

######  Remark C.8.

Thus, in summary, we start with a $d$ variable good resilient function $g$,
take its dual $f$ and then recursively amplify to obtain $f^{u}$ on $d^{u}$
variable. Then we obtain $g^{u}=f^{u}\oplus\mathcal{L}_{d^{u}}$ which is the
final highly recursive function.

We can also have an algebraic degree-resiliency tradeoff. Algebraic degree is
the maximum size of the monomials in the ANF of a function (the maximum number
of variables in a product term). Higher algebraic degree is needed to protect
a system against algebraic degree attack, where as high resiliency protects
the system against correlation attack, two of the most powerful attacks in
cryptanalysis of ciphers. In this construction we can also control whether the
resultant function should be fully sensitive (using Theorem B.1) or should it
have lower sensitivity value and this does not affect the possible resiliency
and algebraic degree values.

###  C.1 Superlinear Separation Between $n$ and ${\sf pdeg}(f)$ For Constant
Order Sensitivity

First we observe how high can sensitivity order be for a function with less
than $n$ polynomial degree. It is easy to see that if a function is $n$-th
order sensitive then its real polynomial degree is also $n$. This is because a
function can be $n$-th order sensitive if for a point
$\mathbf{a}\in\mathbb{F}_{2}^{n}$, $f(\mathbf{a})=0$ and
$f(\mathbf{x})=1,\leavevmode\nobreak\
\forall\mathbf{x}\in\mathbb{F}_{2}^{n}\setminus\\{\mathbf{a}\\}$. Then such a
function will have an odd number of ones in its truth table and thus will have
${\sf pdeg}(f)=n$.

The first separation between $n$ and polynomial degree can be found for
$(n-1)$-th order sensitivity when $n$ is odd, and for $(n-2)$-th order,
otherwise.

######  Lemma C.9.

The maximum value of $k$ such that there exists a $k$-th order sensitive
function with polynomial degree less than $n$ is $n-1$, where $n$ is odd, and
$n-2$, otherwise.

######  Proof C.10.

We prove this result via the resiliency idea. The dual of an
$(n,k,n-1)$-function is an $[n,k,0]$-function, which is a balanced $k$-th
order dual sensitive function.

Let $g$ be an $(n-1)$-th order dual sensitive function with respect to a point
$\mathbf{y}\in\mathbb{F}_{2}^{n}$. Without loss of generality we assume that
$f(\mathbf{y})=0$. Then, corresponding to all the points that can be obtained
by flipping an odd number of bits, the output is $0$, and $1$, otherwise,
where the maximum number bits that can be flipped is $n-1$. That is,
$g(\overline{\mathbf{y}})$ can be both zero or one, which does not affect the
sensitivity order, and the output corresponding to all other $2^{n}-1$ points
is fixed.

Case $n$ odd: The minimum number of points $\mathbf{x}$ for which
$f(\mathbf{x})$ must be zero is

$1+\binom{n}{1}+\binom{n}{3}+\cdots+\binom{n}{n-2}=2^{n-1}.$

We can then fix $f(\mathbf{y})=1$ and the other $2^{n-1}-1$ points have output
$1$, by definition, which gives us an $(n-1)$-th order dual sensitive
$0$-resilient function whose dual $f=g\oplus\mathcal{L}_{n}$ is then an
$(n,n-1,n-1)$-function.

Case $n$ even: Here, the minimum number of points $\mathbf{x}$ for which
$f(\mathbf{x})=0$ is

$1+\binom{n}{1}+\binom{n}{3}+\cdots+\binom{n}{n-1}=2^{n-1}+1$

and thus the corresponding function cannot be balanced.

On the other hand if we try to form an $(n-2)$-th order dual sensitive
function, then the restriction reduces by $\binom{n}{n-1}$ and becomes
$2^{n-1}-n+1$. Meanwhile, the restriction on the minimum number of points with
$f(\mathbf{x})=1$ remains the same and then the remaining $n-1$ points can be
fixed accordingly to make the function balanced, which gives us an
$[n,n-2,0]$-function whose dual is an $(n,n-2,n-1)$-function.

Then our result of super-linear separation between $n$ and ${\sf pdeg}()$
follows from our modified recursive amplification construction.

######  Theorem C.11.

Given any constant $k$ there exists a $k$-th order sensitive function $f$ on
$n$ variables such that ${\sf pdeg}(f)=n^{\frac{\log k}{\log k+1}}$, if $k$ is
even and ${\sf pdeg}(f)=n^{\frac{\log k+1}{\log k+2}}$, if $k$ is odd.

######  Proof C.12.

Given any $k$, we form a function $f$ in the following manner:

  * •

If $k$ is even we form a $(k+2)$-variable balanced $k$-th order dual sensitive
function $g$ which is a $[k+2,k,0]$-function as per Lemma C.9. Then we take
its dual $f=g\oplus\mathcal{L}_{n}$, which is a $(k+2,k,k+1)$-function.

  * •

If $k$ is odd we form a $(k+1)$-variable balanced $k$-th order dual sensitive
function $g$ which is a $[k+1,k,0]$-function. Then we take its dual
$f=g\oplus\mathcal{L}_{n}$, which is a $(k+1,k,k)$-function, via Lemma C.9.

Next we use the recursive amplification process described in Theorem B.1. This
gives a $\left({(k+2)}^{u},k,{(k+1)}^{u}\right)$-function, when $k$ is even
and a $\left({(k+1)}^{u},k,{k}^{u}\right)$-function, otherwise, which gives us
the desired super-linear advantage.

##  Appendix D Results in Section 4

###  D.1 Sufficient Conditions for $s(f)=n$

######  Lemma D.1.

Let us denote by $\mathbb{MM}_{n}$ the set of MM type functions with the
following conditions.

  1. 1.

$\phi(\bm{1}_{n_{1}})=\bm{1}_{n_{2}}$ and $g(\bm{1}_{n_{1}})=0$.

  2. 2.

$wt\left(\phi(\bm{1}_{n_{1}}^{i})\right)\equiv 1\bmod 2$ and
$g(\bm{1}_{n_{1}}^{i})\equiv n_{2}\bmod 2$.

Then for any function $f\in\mathbb{MM}_{n}$ we have $s(f)=n$.

######  Proof D.2.

It suffices to show that $s(f,\bm{1}_{n})=n$. By definition we have
$\phi(\bm{1}_{n_{1}})=\bm{1}_{n_{2}}$. Thus for any input of the form
$\bm{1}_{n_{1}}||\mathbf{y}$ we have
$f(\bm{1}_{n_{1}}||\mathbf{y})=\bigoplus_{i=1}^{n_{2}}y_{i}$. Then if
$y_{i}=1$, for all $i$, we get $f(\bm{1}_{n_{1}}||\bm{1}_{n_{2}})=n_{2}\bmod
2$. Corresponding to this point, if any one of the components in $\mathbf{y}$
is flipped, then the function evaluates to $n_{2}+1\bmod 2$.

If any of the points (say $x_{i}:1\leq i\leq n_{1}$) in $\mathbf{x}$ is
flipped then the output of the function is
$f(\bm{1}_{n_{1}}^{i}||\bm{1}_{n_{2}})$. Since the number of variables of the
linear functions is odd and $g(\bm{1}_{n_{1}}^{i})\equiv n_{2}\bmod 2$ we have
$f(\bm{1}_{n_{1}}^{i}||\bm{1}_{n_{2}})=n_{2}+1\bmod 2$.

###  D.2 An MM function with $s(f)=n$ and ${\sf pdeg}(f)\leq n-1$

Let us first denote some notations that we shall use in the proof. We denote
by $\bf{X_{i}^{j}}$ the monomial $\left(\prod_{k=i}^{j}x_{k}\right)$ and by
$\bf{X^{i}}$ the monomial $\left(\prod_{k=1}^{i}x_{k}\right)$. We define the
polynomial ${\bf L_{n_{2}}}=\prod_{i=1}^{n_{2}}(1-2y_{i}).$ Then we can write
$\mathcal{L}_{{\bf 1_{n_{2}}},0}=\frac{1-\bf{L_{n_{2}}}}{2}$ and
$\mathcal{L}_{{\bf 1_{n_{2}}},1}=\frac{1+\bf{L_{n_{2}}}}{2}$.

######  Theorem D.3.

Let $f\in\mathbb{MM}_{n}$ be an MM function defined on $n=n_{1}+n_{2}$
variables so that $n_{1}\leq n_{2}\leq n_{1}+1$ with $n_{2}\equiv 0\bmod 2$.
If $f$ is defined using $\phi(\bm{1}_{n_{1}-2}00)=\bm{1}_{n_{2}}$,
$g(\mathbf{x})=\prod_{i=1}^{n_{1}-2}x_{i}(1-x_{n-1})(1-{x_{n}})$, the
sensitivity of $f$ is $n$ and the polynomial degree is at most $n-1$.

######  Proof D.4.

First we have $s(f)=n$, which follows directly from the constraints described
and the subsequent proof of Lemma D.1. As $n_{2}$ is even,
$g(\bm{1}_{n_{1}}||\bm{1}_{n_{1}})$ should be $0$, which it is, as the only
point in $\mathbf{x}$ for which $g(\mathbf{x}||\mathbf{y})=1$ is
$\bm{1}_{n_{1}-2}00$.

We now show that ${\sf pdeg}(f)=n-1$. Apart from the constraints given, we
have two more constraints as $f\in\mathbb{MM}_{n}$, namely,
$wt(\phi(\bm{1}_{n_{1}}^{i}))\equiv 1\mod 2$,
$\phi(\bm{1}_{n_{1}})=\bm{1}_{n_{2}}$. We have defined the real polynomial
$p(\mathbf{x},\mathbf{y})$ that represents $f$ in Proposition 4.4. The degree
of the polynomial is $\leq\max(wt(\phi))+n_{1}$. We know that
$p(\mathbf{x},\mathbf{y})=\sum_{a\in\\{0,1\\}^{n_{1}}}\mathcal{P}_{a}(\mathbf{x})\left(\mathcal{L}_{(\phi(\mathbf{a}),g(\mathbf{a}))}(\mathbf{y})\right)$
has monomials of degree $n$ only in the terms $\mathcal{L}_{b,c}$ where
$wt(b)=n_{2}$, which is the case only when $b=\bm{1}_{n_{1}-2}00$ or
$\bm{1}_{n_{1}}$. Additionally $g(\bm{1}_{n_{1}-2}00)=1$ and
$g(\bm{1}_{n_{1}})=0$. Therefore, we can write the polynomial as

$\displaystyle
p(\mathbf{x},\mathbf{y})=p^{\prime}(\mathbf{x},\mathbf{y})+\mathcal{P}_{(\bm{1}_{n_{1}-2}00)}(\mathbf{x})\mathcal{L}_{\phi(\bm{1}_{n_{1}-2}00),g(\bm{1}_{n_{1}-2}00)}(\mathbf{y})+\mathcal{P}_{(\bm{1}_{n_{1}})}(\mathbf{x})\mathcal{L}_{\phi(\bm{1}_{n_{1}}),g(\bm{1}_{n_{1}})}(\mathbf{y})$
$\displaystyle\text{ where
}p^{\prime}(\mathbf{x},\mathbf{y})=\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}\setminus\leavevmode\nobreak\
\\{\bm{1}_{n_{1}},\bm{1}_{n_{1}-2}00\\}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\left(\mathcal{L}_{(\phi(\mathbf{a}),g(\mathbf{a}))}(\mathbf{y})\right).$

Thus in this case ${\sf pdeg}(p^{\prime})=n-1$. Now, expanding
$p(\mathbf{x},\mathbf{y})$ we get

$\displaystyle p(\mathbf{x},\mathbf{y})=$ $\displaystyle
p^{\prime}(\mathbf{x},\mathbf{y})+\left(\prod\limits_{i=1}^{n_{1}-2}\mathbf{x}_{i}\right)(1-x_{n_{1}-1})(1-x_{n_{1}})\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})+\left(\prod_{i=1}^{n_{1}}x_{i}\right)\mathcal{L}_{(\bm{1}_{n_{2}},0)}(\mathbf{y})$
$\displaystyle=p^{\prime}(\mathbf{x},\mathbf{y})+{\bf
X^{n_{1}-2}}(1-x_{n_{1}-1}-x_{n_{1}}+x_{n_{1}-1}x_{n_{1}})\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})+{\bf
X^{n_{1}}}\mathcal{L}_{(\bm{1}_{n_{2}},0)}(\mathbf{y})$
$\displaystyle=p^{\prime}(\mathbf{x},\mathbf{y})+\left({\bf
X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})$
$\displaystyle+{\bf
X^{n_{1}}}\left(\mathcal{L}_{(\bm{1}_{n_{2}},0)}(\mathbf{y})+\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})\right)$
$\displaystyle=p^{\prime}(\mathbf{x},\mathbf{y})+\left({\bf
X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})+{\bf
X^{n_{1}}}.$

In this case, the polynomial degree of the terms are:

  * •

$p^{\prime}(\mathbf{x},\mathbf{y})$ has a degree of at most $n-1$;

  * •

$\left({\bf X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})$
has a degree of $n-1$.

  * •

the degree of $X^{n_{1}}$ is $n_{1}$.

Thus, the polynomial degree of $p(\mathbf{x},\mathbf{y})$ is at most $n-1$ and
the proof is complete.

In this case, any function in $\mathbb{MM}_{n}$ with the added constraint that
$\phi(\bm{1}_{n_{1}-1}00)=\bm{1}_{n_{2}}$ and
$g(\mathbf{x})=\left(\prod_{i=1}^{n_{1}-2}x_{i}\right)(1-x_{n_{1}-1})(1-x_{n})$
would have this property of $s(f)=n$ and ${\sf pdeg}(f)=n-1$. Except for
$\bm{1}_{n_{2}}00$ and $\bm{1}_{n_{2}}$, all the points can have any linear
function of weight less than $n_{2}$, with the only restriction being that
$n_{1}$ points in $\mathbf{x}$ should have odd weighted linear functions
attached to them. This gives us a loose lower bound on the number of functions
that we can recover with this construction technique with the given property.
We can in fact construct $2^{{\sf EXP}(n)}$ functions with such property,
which we state next. Let us now look at an example function.

We let $n=7$ and $n_{1}=3,n_{2}=4$ and show the structure of the Boolean
function. Observe that for the inputs $001$, $011$ and $110$ in $\mathbf{x}$
the corresponding linear function contains only a single variable and the
linear function corresponding to $111$ contains $4$ variables, implying that
$f$ is in the class $\mathbb{MM}_{7}$. Additionally the linear function at
$100$ is the complement of the linear function at $111$, which satisfies the
conditions of Theorem D.3.

$\mathbf{x}$ | The linear function on $\mathbf{y}$
---|---
$000$ | $y_{2}\oplus y_{3}$
$001$ | $y_{1}$
$010$ | $y_{2}$
$011$ | $y_{1}\oplus y_{2}$
$100$ | $y_{1}\oplus y_{2}\oplus y_{3}\oplus y_{4}\oplus 1$
$101$ | $y_{1}\oplus y_{3}$
$110$ | $y_{3}$
$111$ | $y_{1}\oplus y_{2}\oplus y_{3}\oplus y_{4}$
Table 1: A Boolean function $f$ with $D(f)=7$ and ${\sf pdeg}(f)=6$.

######  Corollary D.5.

For any $n$, there are at least $\Omega\left(2^{2^{\frac{n}{2}}}\right)$ MM
type functions with $D(f)=n$ and ${\sf pdeg}(f)=n-1$.

######  Proof D.6.

By definition we have $\lceil\frac{n}{2}\rceil\leq
n_{2}\lceil\frac{n}{2}\rceil+1$. For simplicity, let us assume that $n$ is
even. Then each distinct mapping $\phi$ that satisfies the constraint of
Theorem D.3 will represent an MM type function with $s(f)=n$ and ${\sf
pdeg}(f)=n-1$. We have already defined $\phi$ at the points
$\bm{1}_{n_{1}-2}00$ and $\bm{1}_{n_{1}}$. Let us consider the mapping where
$\phi(\bm{1}_{n_{1}}^{i})={0}_{n_{2}}^{i}$. That is, the function attached
corresponding to the $i$-th critical point ($1\leq i\leq n$) is $y_{i}$ and
since $n_{2}>n_{1}$, this is feasible. Therefore, corresponding to the other
$2^{\frac{n}{2}}-2-\frac{n}{2}$ points in $\mathbf{x}$ we can put any of the
$2^{\frac{n}{2}}$ linear functions defined on $\mathbf{y}$, and each such
function would have the desired property.

Thus, the number of such functions will be
$\left(2^{\frac{n}{2}}-2-\frac{n}{2}\right)^{2^{\frac{n}{2}}}$, which we
denote by $C(n,n-1)$. Then for $n>6$ we have

$C(n,n-1)>\left(2^{\frac{n}{2}-1}\right)^{2^{\frac{n}{2}}}=\Omega\left(2^{2^{\frac{n}{2}}}\right).$

###  D.3 Logarithmic separation Between $n$ and ${\sf pdeg}(f)$ with $s(f)=n$

We finally design a method of constructing an MM type function in
$\mathbb{MM}_{n}$ that has polynomial degree of $n-\Theta(\log n)$. Before
proceeding to the proof, we derive some more results related to the structure
of different polynomials and their interaction upon addition. In the last
subsection we observed how given an MM type function $f$, where $\phi$ and $g$
are defined to be zero in many points, say all points of the form
$\bm{1}_{k_{1}}\bm{0}_{k_{2}}\mathbf{t}\in\mathbb{F}_{2}^{n_{1}}$ then adding
a polynomial term of the form
$\left(\prod_{i=1}^{k_{1}}x_{i}\prod_{j=k_{1}+1}^{k_{2}}(1-x_{j})\right)\mathcal{L}_{\mathbf{b},c}(\mathbf{y})$
transforms it to another MM type function $f^{\prime}$ whose map
$\phi^{\prime}$ and sub-function on $g^{\prime}$ differs from $f$ only for the
points $\bm{1}_{k_{1}}\bm{00}_{k_{2}}\mathbf{t}\in\mathbb{F}_{2}^{n_{1}}$.
With these observations in mind we analyze a function
$f_{1}\in\mathbb{MM}_{n}$ such that its polynomial satisfies the constraint of
Theorem D.3 and then further add some constraints so as to be able to make
modifications as discussed in Proposition 4.6. We define the corresponding map
$\phi_{1}$ and sub-function $g_{1}$ in the lines of Theorem D.3:

$\begin{split}\phi_{1}(\mathbf{x})&=\begin{cases}\bm{1}_{n_{2}}&\text{ if
$\mathbf{x}=\bm{1}_{n_{1}}$ or $\mathbf{x}=\bm{1}_{n_{1}-2}00$}\\\
\bm{0}_{n_{2}}^{i}&\text{ if $\mathbf{x}=\bm{0}_{n_{1}}^{i}$}\\\ 0&\text{
otherwise,}\end{cases}\\\
g_{1}(\mathbf{x})&=\left(\prod_{i=1}^{n_{1}-2}x_{i}\right)(1-x_{n_{1}-1})(1-x_{n_{1}}).\end{split}$
(6)

This definition differs from the function in Theorem D.3 in that the map
$\phi_{1}$ is defined as $0$ in all but $n_{1}+2$ positions. However it
satisfies all the constraints of Theorem D.3. This means that the real
polynomial corresponding to $f_{0}$ can be expressed as

$\displaystyle p_{1}(\mathbf{x},\mathbf{y})$
$\displaystyle=p_{1}^{\prime}(\mathbf{x},\mathbf{y})+\left({\bf
X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)\mathcal{L}_{(\bm{1}_{n_{2}},1)}(\mathbf{y})+{\bf
X^{n_{1}}}$ $\displaystyle=p_{1}^{\prime}(\mathbf{x},\mathbf{y})+\left({\bf
X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)\frac{1+\bf{L_{n_{2}}}}{2}+{\bf X^{n_{1}}},$

where $p_{1}^{\prime}(\mathbf{x},\mathbf{y})$ defined in the same manner as
$p^{\prime}$ in Theorem D.3. Consider the term $-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}-1}\frac{1+\bf{L_{n_{2}}}}{2}$ which has a degree of
$n-1$. If we add the polynomial ${\bf
X_{1}^{n_{1}-4}}(1-x_{n_{1}-3})(1-x_{n_{1}-2})x_{n_{1}-1}\frac{1-\bf{L_{n_{2}}}}{2}$
to this term we get

$\displaystyle{\bf
X_{1}^{n_{1}-4}}(1-x_{n_{1}-3}-x_{n_{1}-2}+x_{n_{1}-3}x_{n_{1}-2})x_{n_{1}-1}\frac{1-\bf{L_{n_{2}}}}{2}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}-1}\frac{1+\bf{L_{n_{2}}}}{2}$ $\displaystyle={\bf
X_{1}^{n_{1}-4}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-4}}x_{n_{1}-3}x_{n_{1}-1}\frac{1-\bf{L_{n_{2}}}}{2}-{\bf
X_{1}^{n_{1}-4}}x_{n_{1}-2}x_{n_{1}-1}\frac{1-\bf{L_{n_{2}}}}{2}$
$\displaystyle+{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}\frac{1-\bf{L_{n_{2}}}}{2}-{\bf
X_{1}^{n_{1}-1}}\frac{1+\bf{L_{n_{2}}}}{2}+{\bf
X_{1}^{n_{1}-1}}\frac{1-\bf{L_{n_{2}}}}{2}$ $\displaystyle=\left({\bf
X_{1}^{n_{1}-4}}x_{n_{1}-1}-{\bf X_{1}^{n_{1}-4}}x_{n_{1}-3}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-4}}x_{n_{1}-2}x_{n_{1}-1}\right)\frac{1-\bf{L_{n_{2}}}}{2}+{\bf
X_{1}^{n_{1}-1}}.$

This polynomial has degree $n-2$, which reduces the degree of the polynomial
by $1$ and creates $2$ terms of the same type of degree $n-2$ and one of
degree $n-3$. Similarly, if we could modify the other degree $n-1$ polynomial
in the same way it would bring down the overall degree of the real polynomial
of the function to $n-2$. This modification is central to our construction
method and we now generalize it, starting with defining two generic polynomial
structures:

  1. 1.

$\hat{p}(i,s)=(\prod_{j=1}^{i}x_{j})(1-x_{i+1})(1-x_{i+2})(\prod_{j=s_{i}}x_{j}),s\subset[n]\setminus[i+2]$,

  2. 2.

$\tilde{p}(i,u)=(\prod_{j=1}^{i}x_{j})(\prod_{j=u_{i}}x_{j}),u\subset[n]\setminus[i].$

From these definitions we get the following two relations.

${\sf pdeg}(\tilde{p}(i,u))={\sf pdeg}(\hat{p}(i-2,u))=i+\lvert u\rvert,$ (7)
$\tilde{p}(i,u)=\tilde{p}(i-k,u^{k})\text{ where }u^{k}=u\cup\\{i,i-1,\ldots
i-k+1\\}.$ (8)

Then corresponding to any $\tilde{p}(i,u)\frac{1+\bf{L_{n_{2}}}}{2}$, we have

$\displaystyle\tilde{p}(i,u)\frac{1+\bf{L_{n_{2}}}}{2}+\hat{p}(i-2,u)\frac{1-\bf{L_{n_{2}}}}{2}$
(9) $\displaystyle=$
$\displaystyle\tilde{p}(i-2,u)\frac{1+\bf{L_{n_{2}}}}{2}-\tilde{p}(i-2,u)x_{i-1}\frac{1+\bf{L_{n_{2}}}}{2}-\tilde{p}(i-2,u)x_{i}\frac{1+\bf{L_{n_{2}}}}{2}+\tilde{p}(i,u)$
$\displaystyle=$
$\displaystyle\tilde{p}(i-2,u)\frac{1+\bf{L_{n_{2}}}}{2}-\tilde{p}(i-2,u_{1})\frac{1+\bf{L_{n_{2}}}}{2}-\tilde{p}(i-2,u_{2})\frac{1+\bf{L_{n_{2}}}}{2}+\tilde{p}(i,u),$

where $\lvert u_{1}\rvert=\lvert u_{2}\rvert=\lvert u+1\rvert$. Then this
addition of the polynomial $\hat{p}(i-2,u)\frac{1-\bf{L_{n_{2}}}}{2}$ reduces
the degree of the polynomial by $1$ and forms two similar terms of degree $1$
less, one term of degree $2$ less, and one term that is only defined on
$\mathbf{x}$ and therefore has degree less than $n_{1}$. Next we note another
property of $\hat{p}$ before proceeding with the final proof.

######  Lemma D.7.

Corresponding to the polynomial $p_{1}$ of an MM function $f_{1}$ where
$\phi_{1}$ is nonzero in only the points $\bm{1}_{n_{1}}$, $\bm{1}_{n_{1}-2}$,
$\bm{0}_{n_{1}}^{i}$ such that $f_{1}\in\mathbb{MM}_{n}$ ($s(f,\bm{1}_{n})=n$)
then adding of any arbitrary number of polynomial terms
$\hat{p}(i,u)(\frac{1\pm\bf{L_{n_{2}}}}{2})$ to $p_{1}$ transforms it to
another MM Boolean function in $\mathbb{MM}_{n}$, provided that for any two
added polynomial terms $\hat{p}(i_{1},u_{1})$ and $\hat{p}(i_{2},u_{2})$ we
have $\lvert i_{1}-i_{2}\rvert\geq 2$ and $i<n_{1}-2,\leavevmode\nobreak\
\forall\,\hat{p}(i,u)$.

######  Proof D.8.

Consider any two $\hat{p}(i_{1},u_{1})$ and $\hat{p}(i_{2},u_{2})$ with
$i_{1}\leq i_{2}-2$. Then, from Equation (2) we have that adding
$\hat{p}(i_{1},u_{1})(\frac{1\pm\bf{L_{n_{2}}}}{2})$ and
$\hat{p}(i_{2},u_{2})(\frac{1\pm\bf{L_{n_{2}}}}{2}$) to a polynomial
corresponding to an MM function only works (the resultant function is still in
$\mathbb{MM}_{n}$) if $\phi(\mathbf{x})=0$ for all $\mathbf{x}$ such that
$\hat{p}(i_{1},u_{1})(\mathbf{x})=1$ or $\hat{p}(i_{2},u_{2})(\mathbf{x})=1$
and moreover $\hat{p}(i_{1},u_{1})$ and $\hat{p}(i_{1},u_{2})$ should not both
return $1$ for any input $\mathbf{x}$.

The first condition is true as any polynomial of the type $\hat{p}(i,u)$ can
only return $1$ if both $x_{i+1}$ and $x_{i+2}$ are set to $0$. This cannot
happen for any critical point as their weight is minimum $n_{1}-1$. And since
we have defined $i<n_{1}-2$ none of these polynomials can return $1$ for the
point $\bm{1}_{n_{1}-2}00$.

Also for any two polynomials $p_{1}=\hat{p}(i_{1},u_{1})$ and
$p_{2}=\tilde{p}(i_{2},u_{2})$ with $i_{1}\leq i_{2}-2$ they cannot both be
$1$ for any input $\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}$ for the simple reason
that for $p_{1}(\mathbf{x})$ to be $1$, $x_{i_{1}}$ and $x_{i_{1}+1}$ should
be set as $1$ and for $p_{2}(\mathbf{x})$ to be $1$ both $x_{i_{1}}$ and
$x_{i_{2}}$ should be set to $0$, by definition. This completes the proof.

Finally, we use the results and equations we have defined so far to develop a
stepwise construction technique to obtain a function with $s(f)=n$ and ${\sf
pdeg}(f)=n-\Theta(\log n)$.

######  Theorem D.9.

There exists a Boolean function $f\in\mathbb{MM}_{n}$ with ${\sf
pdeg}(f)=n-\Theta(\log n)$.

######  Proof D.10.

We define the function $f_{1}$ as in Equation (6) and the corresponding
polynomial is $p_{1}=p_{1}^{\prime}(\mathbf{x},\mathbf{y})+\left({\bf
X_{1}^{n_{1}-2}}-{\bf X_{1}^{n_{1}-2}}x_{n_{1}-1}-{\bf
X_{1}^{n_{1}-2}}x_{n_{1}}\right)(\frac{1+\bf{L_{n_{2}}}}{2})+{\bf
X_{1}^{n_{1}}}$ where $\deg(p^{\prime})=n_{1}+1$.

We start with $f_{1}$ and recursively reduce the polynomial degree by adding
polynomials of the form $\hat{p}(i,u)$ where $i$ starts with $n_{1}-3$ and
decreases by $2$ with every new polynomial that we add. The terms ${\bf
X_{1}^{n_{1}-2}}(\frac{1+\bf{L_{n_{2}}}}{2})$, ${\bf
X_{1}^{n_{1}-2}}x_{n_{1}}(\frac{1+\bf{L_{n_{2}}}}{2})$ and ${\bf
X_{1}^{n_{1}-2}}x_{n_{1}-1}(\frac{1+\bf{L_{n_{2}}}}{2})$ can all be expressed
as polynomials $\tilde{p}(i,u_{i})(\frac{1\pm\bf{L_{n_{2}}}}{2})$ for some
$u_{i}$. Here $i=n_{1}-2$. We also know from Equation (7) that any such
polynomial can also be represented as some
$\tilde{p}(i-k,u_{i}^{k})(\frac{1\pm\bf{L_{n_{2}}}}{2})$.

Then corresponding to the term
$(-1)^{c}\tilde{p}(i-k,u_{i}^{k})(\frac{1+(-1)^{d}\bf{L_{n_{2}}}}{2})$ we add
the polynomial
$\hat{p}(i-k-2,u_{i}^{k})(\frac{1+(-1)^{c+d+1}\bf{L_{n_{2}}}}{2})$ and this
results in at most $3$ new polynomial terms of the form
$\tilde{p}(i-k-1,{u_{i}^{k}}^{\prime})$ of degree at least one less
(specifically one polynomial of degree $2$ less and two polynomials of degree
$1$ less). For each new polynomial we add, if the last polynomial that we
added was $\hat{p}(i,u)(\frac{1\pm\bf{L_{n_{2}}}}{2})$, then the next
polynomial is $\hat{p}(i-2,u^{\prime})(\frac{1\pm\bf{L_{n_{2}}}}{2})$, where
$u$ and $u^{\prime}$ depend on the lower degree polynomials that form.
Therefore for any defined $n_{1}$ we can at most add
$\lfloor\frac{n_{1}-2}{2}\rfloor$ polynomials. This polynomial term addition
is valid and the modified function is still in $\mathbb{MM}_{n}$ as we have
shown in Lemma D.7.

At the first step we have $3$ such polynomial terms to which we add a
$\hat{p}$ polynomial. Then, at the $i$-th step, if we have $3^{i}$ polynomials
of the form $\tilde{p}$ of degree $n-i$. Corresponding to each such, we add
polynomials $\hat{p}(k,u)$ where $n_{1}-3^{i}\geq k\geq n_{1}-3^{i+1}$ for
each polynomial $\tilde{p}(k+2,u)$, and this would form $3^{i+1}$ polynomials
of degree at most $n-(i+1)$. This step can at most be continued for $z$
iterations, where $\sum_{i=1}^{z}2\times 3^{z}\leq n_{1}-1$, that is,
$z\leq\log_{3}(n_{1}-1)$. If we fix $n_{1}=\frac{n}{2}$ this gives us a
function in $\mathbb{MM}_{n}$ with polynomial degree
$n-\log_{3}(\frac{n}{2})=n-\Theta(\log n)$.

It is easy to see that when we have not used some $k$ bits of $\mathbf{x}$ as
the zero bits in $\hat{p}$, our modifications do not affect the map $\phi$ in
the point with at least any two of those $k$-bits being zero. This gives us
the following corollary.

######  Corollary D.11.

There are $\Omega\left(2^{2^{k}}\right)$ functions in $\mathbb{MM}_{n}$ with
polynomial degree $n-\log_{3}(\frac{n}{2})+\log_{3}(k)$ that we can recover
using the construction method of Theorem D.9.

##  Appendix E Super-constant sensitivity with MM functions

###  E.1 Proof of Lemma 4.7

######  Proof E.1.

We have ${\sf sym}^{k}_{m}(\bm{0}_{m})=0$ by definition. Now it suffices to
see for any input point $\mathbf{b}\in\mathbb{F}_{2}^{m}$ that can be obtained
by flipping $i\leq k$ bits of $\bm{0}_{m}$ returns true for an odd number of
monomials of ${\sf sym}^{k}_{m}$, in which case we will have ${\sf
sym}^{k}_{m}(\mathbf{b})=1$. This can be verified as follows.

Any input point obtained by flipping $i$ points in $\bm{0}_{m}$ has exactly
$i$ variables set as one and the rest as zero. These $i$ values will return 1
for $i$ monomials of degree $1$, ${i\choose 2}$ monomials of degree $2$, and
so on. Thus the total number of monomials for which it will return $1$ is
$\sum_{j=1}^{i}{i\choose j}=2^{i}-1$, which is odd for all values of $i>0$.
This completes the proof.

###  E.2 Proofs of Constructions 2 and 3

######  Lemma E.2.

Any function $f:\mathbb{F}_{2}^{n_{1}+n_{2}}\rightarrow\mathbb{F}_{2}$ with
the algebraic normal form $\displaystyle
f(\mathbf{x},\mathbf{y})=\bigoplus_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\left(ac_{\mathbf{a}}(\mathbf{x})\cdot
g_{\mathbf{a}}(\mathbf{y})\right),$ where $g_{\bm{1}_{n_{1}}}={\sf
sym}^{k}_{n_{2}}$ and $g_{\mathbf{a}}=1$ for all
$\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}:n_{1}>wt(\mathbf{a})\geq n_{1}-k$ is
$k$-th order sensitive.

######  Proof E.3.

We show that the function is $k$-th order sensitive in the point
$(\mathbf{a},\mathbf{b})=(\bm{1}_{n_{1}},\bm{0}_{n_{2}})$. We have
$f(\bm{1}_{n_{1}},\bm{0}_{n_{2}})={\sf sym}^{k}_{n_{2}}(\bm{0}_{n_{2}})=0$.
Now, we consider any input that can be obtained by flipping at most $k$ bits
of $(\bm{1}_{n_{1}},\bm{0}_{n_{2}})$. There can be two cases.

All bits are flipped in $\mathbf{y}$: In this case the input point is of the
form
$(\mathbf{x}^{\prime},\mathbf{y}^{\prime})=\left(\bm{1}_{n_{1}},\left[\bm{0}_{n_{2}}\right]_{k}\right)$
for which the output is of the form
$f(\mathbf{x}^{\prime},\mathbf{y}^{\prime})={\sf
sym}^{k}_{n_{2}}\left(\left[\bm{0}_{n_{2}}\right]_{k}\right)$ which is $1$
from Lemma 4.7.

At least one bit is flipped in $\mathbf{x}$: Any such point is of the form
$(\mathbf{x}^{\prime},\mathbf{y}^{\prime})=\left(\left[\bm{1}_{n_{1}}\right]_{k},\left[\bm{0}_{n_{2}}\right]_{k-1}\right)$.
Then the output of the function is of the form
$f(\mathbf{x}^{\prime},\mathbf{y}^{\prime})=g_{\left[\bm{1}_{n_{1}}\right]_{k}}(\mathbf{y})=1.$

This shows that the output of the function is flipped if any $1\leq i\leq k$
of the input bits are flipped at the point $(\bm{1}_{n_{1}},\bm{0}_{n_{2}})$.

Finally we extend the technique of Section D.3 to obtain non-constant
separation between number of variables and real polynomial degree in functions
with super-constant order of sensitivity.

######  Theorem E.4.

There exists a $k$-th order sensitive function in $\mathbb{MM}_{n}^{k}$ with
$n-\frac{\log\left(\frac{n}{2}-k\right)-\log{k}}{k}$ real polynomial degree.

######  Proof E.5.

We construct the corresponding function analogous to the result for first
order order sensitive functions defined in Theorem D.9.

We start with partial description of an MM type function
$f:\mathbb{F}_{2}^{n_{1}+n_{2}}\to\mathbb{F}_{2}$ with nonlinear functions in
$\mathbb{F}_{2}^{n_{2}}$ attached to the points in $\mathbb{F}_{2}^{n_{1}}$.
As we have discussed, this function can be written as
$f(\mathbf{x},\mathbf{y})=\bigoplus_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\left(ac_{\mathbf{a}}(\mathbf{x})\cdot
g_{\mathbf{a}}(\mathbf{y})\right)$, where
$g_{\mathbf{a}}:\mathbb{F}_{2}^{n_{2}}\rightarrow\mathbb{F}_{2},\leavevmode\nobreak\
\forall\mathbf{a},$ and the corresponding real polynomial is written as
$p(\mathbf{x},\mathbf{y})=\displaystyle\sum_{\mathbf{a}\in\mathbb{F}_{2}^{n_{1}}}\mathcal{P}_{\mathbf{a}}(\mathbf{x})\hat{g}_{\mathbf{a}}(\mathbf{y})$
where
$\hat{g}_{\mathbf{a}}(\mathbf{y}):\mathbb{F}_{2}^{n_{2}}\rightarrow\mathbb{R}$
is the real polynomial corresponding to $g_{\mathbf{a}}(\mathbf{y})$.

The function $f$ has $g_{\mathbf{a}}$ defined for all points with
$wt(\mathbf{a})\geq n-k$, which consists of $\sum_{i=0}^{k}{k\choose i}$
points, with $g_{\bm{1}_{n_{2}}}={\sf sym^{n}_{k}}$. Let us denote by
$\widehat{sym}^{n}_{k}(\mathbf{y})$ the corresponding real polynomial. Then
the real polynomial corresponding to $\overline{\sf sym^{n}_{k}}$ is
$1-\widehat{sym}^{n}_{k}(\mathbf{y})$.

From this point our construction is analogous to that of Theorem D.9. In case
of first order sensitivity, the polynomial terms we added to reduce the degree
was of the form
$\left(\prod_{i=1}^{j_{1}}(x_{i})(1-x_{j_{1}+1})(1-x_{j_{1}+2})\prod_{j\in
S}x_{j}\right)g(\mathbf{y})$, where
$g(\mathbf{y})\in\\{\frac{1+\bf{L_{n_{2}}}}{2},\frac{1-\bf{L_{n_{2}}}}{2}\\}$
and $S\subseteq[n_{1}]-[j_{1}+2]$ so that high degree polynomial terms cancel
out.

In case of $k$-th order sensitive function, any new polynomial term that we
add will be of form

$T(j,S)=\left(\prod_{i_{1}=1}^{j}(x_{i_{1}})\prod_{i_{2}=j+1}^{j+1+k}\left(1-x_{i_{2}}\right)\prod_{i_{3}\in
S}x_{i_{3}}\right)g(\mathbf{y}),$

where
$g(\mathbf{y})\in\\{\widehat{sym}^{n}_{k}(\mathbf{y}),1-\widehat{sym}^{n}_{k}(\mathbf{y})\\}$
and $S\subseteq[n_{1}]-[j+k+1]$.

Let us suppose the total degree of the constructed polynomials at some point
is $n^{\prime}$. If we add a term of the form $T(j,S)$ that cancels out a
polynomial term of degree $n^{\prime}$, then it creates $k\choose{i-1}$ terms
of degree $n^{\prime}-i$ where $0<i<k$. Moreover with a new polynomial term
that is added, the value of $j$ reduces by $k$ and as we know $j\geq 0$. Then
we have the following lower bound on how much can we reduce the polynomial
degree of the function depending on the value of $k$.

Let us assume the polynomial degree of the function is $n-p$. To reduce the
polynomial degree by $p$ we have to cancel $(2^{k}-1)^{p}$ terms, and adding
such a term will reduce the value of $j$ by $k$. Let us assume that
$n_{1}=\frac{n}{2}$. Then we have

$\displaystyle k\cdot(2^{k}-1)^{p}=\frac{n}{2}-k$ $\displaystyle\implies$
$\displaystyle\log(k)+p\log(2^{k}-1)=\log\left(\frac{n}{2}-k\right)$
$\displaystyle\implies$
$\displaystyle\log(k)+pk\geq\log\left(\frac{n}{2}-k\right)$
$\displaystyle\implies$ $\displaystyle
p\geq\frac{\log\left(\frac{n}{2}-k\right)-\log(k)}{k}.$

Thus, even if we have $k=o(\log n)$ we get a non-constant separation between
number of variables $n$ and the real polynomial degree $n-p$.