11institutetext:  University of California San Diego
11email<EMAIL_ADDRESS>22institutetext: Purdue University
22email<EMAIL_ADDRESS>33institutetext: Indian Statistical Institute,
Kolkata
33email<EMAIL_ADDRESS>44institutetext: Indian Institute of
Technology, Kanpur
44email<EMAIL_ADDRESS>
# Relations between monotone complexity measures based on decision tree
complexity

Farzan Byramji , Work done while FB and VJ were at Indian Institute of
Technology, Kanpur11 Vatsal Jha , * 22 Chandrima Kayal 33 Rajat Mittal 44

###### Abstract

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-
rank conjecture for communication complexity, up to $\log n$ factor, for any
Boolean function composed with $\and$ function as the inner gadget. One of the
main tools in this result was the relationship between monotone analogues of
well-studied Boolean complexity measures like block sensitivity and
certificate complexity. The relationship between the standard measures has
been a long line of research, with a landmark result by Huang (Annals of
Mathematics 2019), finally showing that sensitivity is polynomially related to
all other standard measures.

In this article, we study the monotone analogues of standard measures like
block sensitivity ($\mathsf{mbs}(f)$), certificate complexity
($\mathsf{MCC}(f)$) and fractional block sensitivity ($\mathsf{fmbs}(f)$); and
study the relationship between these measures given their connection with
$\and$-decision tree and sparsity of a Boolean function. We show the following
results:

  * •

Given a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, the ratio
$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}$ is bounded by a function of
$n$ (and not $l$). A similar result was known for the corresponding standard
measures (Tal, ITCS 2013). This result allows us to extend any upper bound by
a _well behaved_ measure on monotone block sensitivity to monotone fractional
block sensitivity.

  * •

The question of the best possible upper bound on monotone block sensitivity by
the logarithm of sparsity is equivalent to the natural question of best upper
bound by degree on sensitivity. One side of this relationship was used in the
proof by Knop, Lovett, McGuire and Yuan (STOC 2021).

  * •

For two natural classes of functions, symmetric and monotone, hitting set
complexity ($\mathsf{MCC}$) is equal to monotone sensitivity.

##  1 Introduction

Decision tree complexity is one of the simplest complexity measure for a
Boolean function where the complexity of an algorithm only takes into account
the number of queries to the input. Various complexity measures based on
decision tree complexity (like quantum query complexity, randomized query
complexity, certificate complexity, sensitivity, block sensitivity and many
more) have been introduced to study Boolean functions (functions from a subset
of $\\{0,1\\}^{n}$ to $\\{0,1\\}$) [6, 2, 16]. Understanding the relations
between these complexity measures of Boolean function has been a central area
of research in computational complexity theory for at least 30 years. Refer to
[6] for an introduction to this area.

Two such complexity measures $M_{1}$ and $M_{2}$ are said to be polynomially
related if there exists constants $c_{1}$ and $c_{2}$ such that
$M_{1}=O(M_{2}^{c_{1}})$ and $M_{2}=O(M_{1}^{c_{2}})$. Recently, Huang [9]
resolved a major open problem in this area known as the “sensitivity
conjecture”, showing the polynomial relationship between the two complexity
measures sensitivity $(\mathsf{s}(f))$ and block sensitivity
$(\mathsf{bs}(f))$ for a Boolean function $f$ (implying sensitivity is
polynomially related to almost all other complexity measures too).

Once two complexity measures have been shown to be polynomially related, it is
natural to ask if the relationships are tight or not. This means, if we can
show $\forall~{}f,~{}M_{1}(f)=O(M_{2}(f))^{\alpha}$, then is there an example
that witnesses the same gap? In other words, does there exists a function $f$
for which $M_{1}(f)=\Omega(M_{2}(f))^{\alpha}$? Figuring out tight relations
between complexity measures based on decision trees has become the central
goal of this research area. ([3] compiled an excellent table with the best-
known relationships between these different measures.)

Additionally, many new related complexity measures have been introduced in
diverse areas, sometimes to understand these relations better [10, 4, 7].
Recently, monotone analogues of such combinatorial measures have been explored
in [11] for studying the celebrated _log-rank conjecture_ in communication
complexity (for definitions of these monotone measures, see section 2).

In particular, Knop et. al. [11] resolved the log rank conjecture (up to
$\log(n)$ factor) for any Boolean function $f$ composed with $\and$ function
as the inner gadget. For such functions, the rank is equal to the sparsity of
the function (denoted by $\mathsf{spar}(f))$ in its polynomial representation
(with range $\\{0,1\\}$). So the log-rank conjecture amounts to proving a
polynomial upper bound of $\log(\mathsf{spar}(f))$ on the deterministic
communication complexity of $(f\circ\wedge_{2})$ i.e.
$D^{cc}(f\circ\wedge_{2})$. As mentioned before, the proof provided in [11]
utilized monotone analogues of the standard combinatorial measures (block
sensitivity, fractional block sensitivity etc.). The reason for considering
monotone measures was due to the observation that the deterministic
communication complexity of such functions is related to their fractional
monotone block sensitivity ($\mathsf{fmbs}$)

$D^{cc}(f\circ\wedge_{2})\leq\mathsf{fmbs}(f)\log(\mathsf{spar}(f))\log(n).$

Fractional block sensitivity (and its relation with block sensitivity) has
been studied before [1, 12, 19, 8]. It seems natural to look at the monotone
analogues of fractional block sensitivity ($\mathsf{fmbs}$) and block
sensitivity ($\mathsf{mbs}$), and see if they can used to upper bound
$\mathsf{fmbs}$ with logarithm of sparsity. They precisely do this, and show
that for every Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$:

  * •

$\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$,

  * •

$\mathsf{fmbs}(f)=O(\mathsf{mbs}^{2}(f))$.

This implies that a sparse Boolean function has small fractional monotone
block sensitivity and in turn small deterministic communication complexity,

$\mathsf{fmbs}(f)=O(\log^{4}(\mathsf{spar}(f)))\Rightarrow
D^{cc}(f\circ\wedge_{2})=O(\log^{5}(\mathsf{spar}(f))\log n).$

Here $\mathsf{spar}(f)$ denotes the sparsity of $f$ as a polynomial with range
$\\{0,1\\}$.

The above proof technique gives rise to a natural question, can these
relationships between monotone and related measures be improved? The main
objective of this article is to explore this question. Specifically, we look
at the following variants.

  * •

Is it possible to improve the exponent in the relationship
$\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$?

  * •

Can we translate the bound on $\mathsf{fmbs}(f)$ by _well behaved quantities_
using their bound on $\mathsf{mbs}(f)$. (Similar to the result of Tal [19]
which allows us to lift upper bounds on block sensitivity to fractional block
sensitivity for many well behaved measures.)

  * •

Are there specific class of functions for which monotone analogues have a
better dependence on sparsity?

Ideally, we would like to compile a table similar to [3] for monotone
measures. We start by giving a preliminary table in Appendix 0.E.

###  1.1 Our Results

We study the monotone analogues of standard complexity measures like block
sensitivity, certificate complexity and their relations with standard
complexity measures.

It is natural to ask if it is possible to improve upper bounds on these
monotone measures? One very interesting approach for improving bounds on
$\mathsf{fbs}(f)$ (standard measure) is by Tal [19]. He showed that the ratio
of $\mathsf{bs}(f^{l})$ and $\mathsf{fbs}(f^{l})$ is bounded by a quantity
independent of $l$; this allowed him to lift _any_ upper bound on
$\mathsf{bs}(f)$ by a measure which is _well behaved with respect to
composition_ to $\mathsf{fbs}(f)$. We prove a similar result for
$\mathsf{mbs}(f)$ and $\mathsf{fmbs}(f)$.

###### Theorem 1.1

Consider a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. For a
sufficiently large $n$, the ratio

$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}\leq p(n)$

for all $l\geq 1$, where $p(n)$ is a function in $n$ independent of $l$.

As mentioned earlier, there is a nice implication of this behaviour (as shown
in [13] for standard measures): given a measure $M$ which _behaves well under
composition_ and an upper bound on monotone block sensitivity in terms of
measure $M$, we can lift the same upper bound to fractional monotone block
sensitivity.

###### Corollary 1

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. Let $M(.)$ be
a complexity measure such that for all $l\geq 2,$ $M(f^{l})\leq
M(f)M(f^{l-1})$. If $\mathsf{mbs}(f)\leq M(f)^{\alpha}$ then
$\mathsf{fmbs}(f)=O(M(f)^{2\alpha})$. Furthermore, if $M(1-f)=O(M(f))$ then
$\mathsf{fmbs}(f)=O(M(f)^{\alpha})$.

We need another extra condition on $M$, $M(1-f)=O(M(f))$, as compared to
Kulkarni and Tal [13]. However, most of the complexity measures should satisfy
this condition trivially.

It is tempting to apply this corollary on $\log(\mathsf{spar}(f))$ and try to
improve the upper bound on $\mathsf{fmbs}(f)$ in terms of
$\log(\mathsf{spar}(f))$. We show a negative result here:
$\log(\mathsf{spar}(f))$ does not behave well under composition, indeed the
sparsity of a composed function $f\circ g$ can depend on the degree of $f$
which can be much larger than the logarithm of the sparsity. Hence, Corollary
1 can not be used to improve the upper bound on $\mathsf{fmbs}(f)$. For the
counterexample, please see Section 3.1.

Although our attempt to improve the bound on $\mathsf{fmbs}{(f)}$ did not bear
success; we asked, is it possible to improve the log-sparsity upper bound on
$\mathsf{mbs}(f)$? For the question of improving the relation
$\mathsf{mbs}(f)=O(\log(\mathsf{spar}(f))^{2})$, we show that it will improve
the upper bound on sensitivity in terms of degree (a central question in this
field).

###### Theorem 1.2

If there exists an $\alpha$ s.t. for every Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
$\mathsf{mbs}(f)=O(\log^{\alpha}{\mathsf{spar}(f)})$, then for every Boolean
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
$\mathsf{s}(f)=O(\mathrm{deg}^{\alpha}(f))$.

The converse of this result follows from the proof of
$\mathsf{mbs}(f)=O(\log(\mathsf{spar}(f))^{2})$ in [11]. Nisan and Szegedy
[16] showed that $\mathsf{s}(f)=O(\mathrm{deg}(f)^{2})$. However, the best
possible separation known is due to Kushilevitz (described in [17]) giving a
function $f$ such that $\mathsf{s}(f)=\Omega(\mathrm{deg}(f)^{1.63})$. So, our
result implies that the best possible bound on monotone block sensitivity in
terms of logarithm of sparsity cannot be better than
$\mathsf{mbs}(f)=O(\log(\mathsf{spar}(f))^{1.63})$.

Going further, we ask if these bounds can be improved for a class of functions
instead of a generic Boolean function? Buhrman and de Wolf [5] proved that the
log-rank conjecture holds when the outer function is monotone or symmetric. It
turns out that all these monotone measures are equal for these classes of
functions.

###### Theorem 1.3

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is either symmetric or monotone, then

$\mathsf{ms}(f)=\mathsf{mbs}(f)=\mathsf{fmbs}(f)=\mathsf{MCC}(f).$

This implies an upper bound of $O(\log^{2}(\mathsf{spar}(f)))$ on
$\mathsf{MCC}$ for these functions. For symmetric functions, this bound can be
improved to $O(\log\mathsf{spar}(f))$ by combining the above relation with the
upper bound on communication complexity for the corresponding AND-functions
[5]. Moreover, Buhrman and de Wolf [5] showed that
$\mathsf{mbs}(f)=\Omega(\log(\mathsf{spar}(f))/\log n)$, which implies that
the upper bound is essentially tight.

#### Organization:

In Section 2 we recall the definitions of standard Boolean complexity measures
as well as state their monotone analogues. In Section 3 we will give the proof
ideas of our results. This section also contains the counterexample which
shows that the relationship between $\mathsf{fmbs}{f}$ and
$\log(\mathsf{spar}(f))$ can’t be improved using this method (Section 3.1).
Section 4 contains the conclusion and some related open problems to pursue.

Appendix 0.A and Appendix 0.B contain the complete proof of Theorem 1.1.
Appendix 0.C contains the equivalence between the problem of upper bounding
$\mathsf{mbs}(f)$ in terms of $\log(\mathsf{spar}(f))$ and the well-studied
problem of upper bounding $\mathsf{s}(f)$ in terms of $\mathrm{deg}(f)$
(Theorem 1.2). Finally, Appendix 0.D shows that for the common classes of
symmetric and monotone Boolean functions $\mathsf{MCC}$ and $\mathsf{mbs}$ are
the same (Theorem 1.3). In Appendix 0.E, we give an overview of the present
scenario of the relationships between monotone measures.

##  2 Preliminaries

For the rest of the paper, $f$ denotes a Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ if not stated otherwise. We start by
introducing the following notations that will be used in the paper:

  * •

$[n]$ denotes the $\\{1,2,...,n\\}$. For a set $C\subseteq[n]$, $|C|$ denotes
its cardinality.

  * •

For a string $x\in\\{0,1\\}^{n}$, its support is defined as
$\mathrm{supp}(x):=\\{i:x_{i}=1\\}$ and $|x|:=|\mathrm{supp}(x)|$ denotes its
Hamming weight .

  * •

For a string $x\in\\{0,1\\}^{n}$, $x^{\oplus i}$ denotes the string obtained
by flipping the $i^{th}$ bit of the string $x$.

  * •

For a string $x\in\\{0,1\\}^{n}$ and a $B\subseteq[n]$, $x^{B}$ denotes the
string obtained by flipping the input bits of $x$ that correspond to $B$.

  * •

Every Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ can be expressed
as a polynomial over $\mathbb{R}$,
$f(x)=\sum_{S\subseteq[n]}\alpha_{S}\prod_{i\in S}x_{i}.$ The sparsity of $f$
is defined as $\mathsf{spar}(f):=|\\{S\neq\emptyset:\alpha_{S}\neq 0\\}|$ and
the degree of $f$ is defined as
$\mathrm{deg}(f):=\underset{S\subseteq[n]:\alpha_{S}\neq 0}{\max}|S|$.

Having introduced the notations, we now recall the definitions of standard
Boolean complexity measures.

######  Definition 1 (Sensitivity)

For an input $x\in\\{0,1\\}^{n}$ the $i^{th}$ bit is said to be sensitive for
$x$ if $f(x^{\oplus i})\neq f(x)$. The sensitivity of $x$ w.r.t $f$ is defined
as

$\mathsf{s}(f,x):=|\\{i\in[n]:f(x^{\oplus i})\neq f(x)\\}|,$

while the sensitivity of $f$ is defined as

$\mathsf{s}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{s}(f,x).$

######  Definition 2 (Block Sensitivity)

For an input $x\in\\{0,1\\}^{n}$, a subset $B\subseteq[n]$ is said to be a
sensitive block for $x$ w.r.t $f$ if $f(x^{B})\neq f(x).$ The block
sensitivity of $f$ at $x$, denoted by $\mathsf{bs}(f,x)$, is defined as

$\mathsf{bs}(f,x)=\max\\{k|\exists B_{1},\dots,B_{k}\textit{ with }B_{i}\cap
B_{j}=\emptyset\textit{ for }i\neq j\textit{ and }f(x^{B_{i}})\neq f(x)\\}.$

Block sensitivity of $f$ is defined as:

$\mathsf{bs}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{bs}(f,x).$

Fractional block sensitivity ($\mathsf{fbs}$) is obtained by allowing
fractional weights on sensitive blocks.

######  Definition 3 (Fractional Block Sensitivity)

Let $W(f,x):=\\{B\subseteq[n]:f(x^{B})\neq f(x)\\}$ denote the set of all
sensitive blocks for the input $x\in\\{0,1\\}^{n}$. The fractional block
sensitivity of f at x, denoted by $\mathsf{fbs}(f,x)$ is the value of the
linear program:

$\mathsf{fbs}(f,x):=\max\sum_{w\in W(f,x)}b_{w}$

s.t.

$\forall i\in[n],\sum_{w\in W(f,x):i\in w}b_{w}\leq 1$

and

$\forall w\in W(f,x),\;b_{w}\in[0,1].$

The fractional block sensitivity of $f$ is defined as:

$\mathsf{fbs}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{fbs}(f,x).$

Note that restricting the linear program for $\mathsf{fbs}(f,x)$ to only
integral values gives $\mathsf{bs}(f,x)$.

######  Definition 4 (Certificate Complexity)

For a function $f$ and an input $x\in\\{0,1\\}^{n}$, a subset $C\subset[n]$ is
said to be a certificate for $x$ if for all $y\in\\{y\in\\{0,1\\}^{n}:\forall
i\in C,\;x_{i}=y_{i}\\}$ we have $f(x)=f(y)$. For a function $f$ and an input
$x\in\\{0,1\\}^{n}$ the certificate complexity of $f$ at $x$, denoted by
$\mathsf{C}(f,x)$, is defined as:

$\mathsf{C}(f,x):=\underset{C:\text{$C$ is a certificate for $x$}}{\min}|C|.$

The certificate complexity of $f$ is defined as:

$\mathsf{C}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{C}(f,x).$

The fractional measures $\mathsf{fbs}$ and $\mathsf{FC}$ were introduced in
[19]. There it was observed that for all $x\in\\{0,1\\}^{n}$ we have :
$\mathsf{fbs}(f,x)=\mathsf{FC}(f,x)$ since the linear program for Fractional
Certificate Complexity and Fractional Block Sensitivity are the primal-dual of
each other and are also feasible.

For each of these standard measures, the analogous monotone versions can be
defined by restricting functions $f$ to the positions in the support of a
given input $x\in\\{0,1\\}^{n}$. Formally, for a function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and an input $x\in\\{0,1\\}^{n}$ let
$f_{x}$ denote the function $f$ obtained by restricting $f$ to the set
$\\{y\in\\{0,1\\}^{n}:\forall i\in\mathrm{supp}(x),\;y_{i}=1\\}$.

######  Definition 5 (Monotone Sensitivity)

The monotone sensitivity for $x$ is defined as
$\mathsf{ms}(f,x):=\mathsf{s}(f_{x},0^{n-|x|})$ while the monotone sensitivity
for $f$ is defined as

$\mathsf{ms}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{ms}(f,x).$

######  Definition 6 (Monotone Block Sensitivity)

The monotone block sensitivity of a function $f$ at an input
$x\in\\{0,1\\}^{n}$ is defined as
$\mathsf{mbs}(f,x):=\mathsf{bs}(f_{x},0^{n-|x|})$ while the monotone block
sensitivity of $f$ is defined as:

$\mathsf{mbs}(f)=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{mbs}(f,x).$

Similar to block sensitivity, fractional block sensitivity of $f$ can be
extended to the monotone setting by defining the linear program over the
sensitive monotone blocks i.e. sensitive blocks containing only $0$’s.

######  Definition 7 (Fractional Monotone Block Sensitivity)

For a function $f$ the fractional monotone block sensitivity at an input
$x\in\\{0,1,\\}^{n}$ is defined as:
$\mathsf{fmbs}(f,x):=\mathsf{fbs}(f_{x},0^{n-|x|})$ and the fractional
monotone block sensitivity of $f$ is defined as:

$\mathsf{fmbs}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{fmbs}(f,x).$

Certificate complexity can also be extended to the monotone setting by
counting only the zero entries in the certificate. The monotone analogue of
certificate complexity was introduced in [11] as hitting set complexity (it
can be viewed as a hitting set for system of monomials). Formally,

######  Definition 8 (Monotone Certificate Complexity/Hitting Set Complexity)

For a function $f$ and an input $x\in\\{0,1\\}^{n}$ the hitting set complexity
for $x$ is defined as:

$\mathsf{MCC}(f,x):=\mathsf{C}(f_{x},0^{n-|x|}),$

while the hitting set complexity of the function $f$ is defined as:

$\mathsf{MCC}(f):=\underset{x\in\\{0,1\\}^{n}}{\max}\mathsf{MCC}(f,x).$

Since $\mathsf{bs}$ allows only integer solutions to $\mathsf{fbs}$ linear
program, and $\mathsf{C}$ only allows integer solutions to the dual linear
program [19],

$\mathsf{bs}(f_{x},0^{n-|x|})\leq\mathsf{fbs}(f_{x},0^{n-|x|})\leq\mathsf{C}(f_{x},0^{n-|x|}),$

By similar arguments,

$\mathsf{mbs}(f,x)\leq\mathsf{fmbs}(f,x)\leq\mathsf{MCC}(f,x).$

Instead of taking maximum over all inputs, these measures can be defined for a
certain output too. In other words, for a complexity measure
$M\in\\{\mathsf{s},\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{ms},\mathsf{mbs},\mathsf{fmbs},\mathsf{MCC}\\}$
and $b\in\\{0,1\\}$,

$M^{b}(f):=\underset{x\in f^{-1}(b)}{\max}M(f,x).$

##  3 Proof Outline

First, we outline the ideas for the proofs of Theorem 1.2 and Theorem 1.3.
Subsequently, we will give proof outline for our main result, Theorem 1.1.

#### Proof idea of Theorem 1.2

We would like to prove that $\mathsf{s}(f)=O(\mathrm{deg}^{\alpha}(f))$ for
any Boolean function $f$ (given that
$\mathsf{mbs}(g)=O(\log^{\alpha}{\mathsf{spar}(g)})$ for all Boolean functions
$g$). The idea is to convert $f$ into $\widetilde{f}$ by shifting the point
with maximum sensitivity to $0^{n}$; this transformation can only decrease the
degree and $\mathsf{mbs}(f)$ is higher than $\mathsf{s}(\widetilde{f})$.

The rest is accomplished by using the fact that sparsity is at most
exponential in degree. This is shown for Boolean functions with $\\{-1,1\\}$
domain first using Parseval’s identity, and then it can be translated for
Boolean functions with $\\{0,1\\}$ domain.

For the interest of space we will present the proof of Theorem 1.2 in Appendix
0.C.

#### Proof idea of Theorem 1.3

We deal with the cases of monotone and symmetric boolean functions separately.

For monotone boolean functions, the idea for showing equality between the
monotone versions of the standard boolean complexity measures is similar to
the approach used for the standard complexity measures i.e. we consider a
string $x$ which achieves the hitting set complexity
$\mathsf{MCC}(f)=\mathsf{MCC}(f,x)$ with $C$ as one of its witness. Now, using
$x$ and $C$ we construct another input $x^{{}^{\prime}}$ with
$\mathrm{supp}(x)\subseteq\mathrm{supp}(x^{{}^{\prime}})$ and
$\mathrm{supp}(x^{{}^{\prime}})\cap C=\phi$ s.t. every bit $i\in C$ is
sensitive for $f_{x}$ at $x^{{}^{\prime}}$. Hence leading to
$\mathsf{MCC}(f,x)\leq\mathsf{ms}(f,x^{{}^{\prime}})\leq\mathsf{ms}(f)$.

Now for the case of symmetric boolean functions, we show that there exists an
input $z\in\\{0,1\\}^{n}$ s.t. $\mathsf{MCC}(f)=\mathsf{MCC}(f,z)$ and
$\mathsf{MCC}(f,z)=n-|z|$, where $|z|$ is the Hamming weight of $z$ i.e.
$|z|=\mathrm{supp}(f)$. But this implies
$\mathsf{ms}(f,z)=\mathsf{s}(f_{z},0^{n-|z|})=n-|z|=\mathsf{MCC}(f,z)=\mathsf{MCC}(f)$.

We will give a complete proof in Appendix 0.D.

###  3.1 $\mathsf{fmbs}$ versus $\mathsf{mbs}$

Let us move to the proof idea of Theorem 1.1, we essentially follow the same
proof outline as [19]. Theorem 1.1 proves that for any
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, the ratio
$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}$ is bounded above by a
function of just $n$ (and independent of $l$). In other words, composition
make $\mathsf{fmbs}$ and $\mathsf{mbs}$ equal in the asymptotic sense.

We will be considering the case of monotone functions and non-monotone
functions separately. While the case for monotone functions is handled easily
due to Theorem 1.3 (we have a stronger relation
$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}=1$), most of the work is
done for the case when $f$ is non-monotone.

#### Proof outline of Theorem 1.1

From the discussion above, assume that $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
is a non-monotone Boolean function. We want to show that

$\mathsf{mbs}(f^{l})\geq p(n)~{}\mathsf{fmbs}(f^{l}),$

for some function $p(n)$ and big enough $l$.

Similar to $\mathsf{fbs}(f)$, $\mathsf{fmbs}(f)$ can also be written as a
fractional relaxation (linear program) of an integer program for
$\mathsf{mbs}(f)$. The proof converts a feasible solution of the linear
program for $\mathsf{fmbs}(f^{l+1})$ into a feasible solution of
$\mathsf{mbs}(f^{l+1})$ without much loss in the objective value, bounding
$\frac{\mathsf{mbs}(f^{l+1})}{\mathsf{fmbs}(f^{l+1})}$ in terms of
$\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}$:

$\mathsf{mbs}(f^{l+1})\geq\mathsf{fmbs}(f^{l+1})\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}\alpha_{l},$
(1)

where $\alpha_{l}$ s.t. $\prod_{l=1}^{\infty}\alpha_{l}=\Omega(1)$. This
finishes the proof by taking large enough $l$. We are left with proving
Equation 1 for some $\alpha_{l}$’s.

Remember, the idea is to convert a solution of $\mathsf{fmbs}(f^{l+1})$ into a
solution of $\mathsf{mbs}(f^{l+1})$. Let
$x:=(x^{1},x^{2},...,x^{n})\in\\{0,1\\}^{n^{l+1}}$ be the input s.t.
$\mathsf{fmbs}(f^{l+1})=\mathsf{fmbs}(f^{l+1},x)$ where
$x^{1},x^{2},...,x^{n}\in\\{0,1\\}^{n^{l}}$. The input $y\in\\{0,1\\}^{n}$ be
the $n$-bit string corresponding to $x$
i.e.$\;\forall\;i\in[n],\;y_{i}:=f^{l}(x^{i})$. We know that
$f^{l+1}(x)=f(y)$.

Let $\\{B_{1},...,B_{k}\\}$ be the set of all minimal monotone blocks for $f$
at $y$. A minimal monotone block, say $B=\\{i_{1},i_{2},\cdots,i_{k}\\}$, of
$y$ gives minimal monotone blocks for $f^{l}$ at inputs
$x^{i_{1}},x^{i_{2}},\cdots,x^{i_{k}}$. Observe that the total weight
contributed by any block $B_{i}$ in the linear program for $f^{l+1}$ will
become feasible for the following linear program:

$\max\sum_{i=1}^{k}w_{i},$

s.t.

$\sum_{j:i\in B_{j}}w_{j}\leq\mathsf{fmbs}(f^{l},x^{i}),\;\forall\;i\in[n],$
$w_{j}\geq 0,\forall j\in[k].$

A small modification to these weights (multiplying by a quantity closely
related to $\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}$ and taking their
integer part) gives the solution of the following integer program (notice that
$\mathsf{mbs}(f^{l})$ is taken over another suitable input $\widehat{x}$):

$\max\sum_{i=1}^{k}w_{i},$

s.t.

$\sum_{j:i\in
B_{j}}w_{j}\leq\mathsf{mbs}(f^{l},\widehat{x}^{i}),\;\forall\;i\in[n],$
$w_{j}\in\\{0,1,2,\dots,\mathsf{mbs}(f^{l})\\},\forall j\in[k].$

Let $\\{w^{{}^{\prime}}_{i}\\}$ be the solution of the program above. Using
this assignment $w^{{}^{\prime}}_{i}$ we can construct
$\sum_{i=1}^{k}w^{{}^{\prime}}_{i}$ many disjoint monotone sensitive blocks of
$f^{l+1}$ (see Appendix 0.A for this construction).

It can be shown that the objective value of the obtained solution satisfies,

$\mathsf{mbs}(f^{l+1})\geq\mathsf{fmbs}(f^{l+1})\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}-2^{n}.$

Here, the term $2^{n}$ appears because we take the integer part of a
fractional solution to construct $\\{w^{{}^{\prime}}_{i}\\}$. This inequality
can be converted into Equation 1 by using properties of composition of
fractional monotone block sensitivity and some minor assumptions on
$\mathsf{mbs}(f)$. We present the complete proof of Theorem 1.1 in Appendix
0.A.

#### Implications of Theorem 1.1

One of the reason Theorem 1.1 is interesting because it provides a way of
lifting upper bounds on $\mathsf{mbs}(f)$ to upper bounds on
$\mathsf{fmbs}(f)$. This was observed by [13] for the standard setting
($\mathsf{bs}$ and $\mathsf{fbs}$), using which they showed the quadratic
relation between $\mathsf{fbs}(f)$ and $\mathrm{deg}(f)$ i.e.
$\mathsf{fbs}(f)=O(\mathrm{deg}^{2}(f))$. This was an improvement over
$\mathsf{fbs}(f)\leq\mathsf{C}(f)=O(\mathrm{deg}^{3}(f))$ [15].

Similarly, we can do the lifting for $\mathsf{mbs}(f)$ and $\mathsf{fmbs}(f)$
which we have stated in 1. We present the proof of 1 in Appendix 0.A.

We now give an example showing that $\log\mathsf{spar}(f^{2})$ may be
exponentially larger than $(\log\mathsf{spar}(f))^{2}$ and so 1 cannot be
applied to $\log\mathsf{spar}$. For any Boolean functions $f$ and $g$,
$\mathsf{spar}(f\circ g)\geq(\mathsf{spar}(g)-1)^{\mathrm{deg}(f)}$ (see, for
instance, [14]111Their proof is stated for sparsity in the Fourier
representation, but is readily seen to work for block composition of arbitrary
multilinear polynomials.). In particular, when $\mathsf{spar}(g)\geq 3$,
$\log\mathsf{spar}(f\circ g)\geq\mathrm{deg}(f)$. So any function $f$
satisfying $\mathsf{spar}(f)\geq 3$ and
$\mathrm{deg}(f)=2^{\Omega(\log\mathsf{spar}(f))}$ gives us the desired
separation. For instance, we may take,

$f(x_{1},x_{2},\dots,x_{n})=\mathsf{OR}(\and(x_{1},x_{2},\dots,x_{n/2}),\and(x_{n/2+1},x_{n/2+2},\dots,x_{n}))$

which has degree $n$ and sparsity only $3$.

##  4 Conclusion

In the present work we studied the behaviour of different monotone complexity
measures and their relation with one another. The relations between these
measures are natural questions by themselves; on top of that, they can
potentially be used to improve the upper bound on deterministic communication
complexity in terms of logarithm of sparsity.

To summarize our results, we were able to show a better upper bound on
$\mathsf{MCC}(f)$ in terms of $\log(\mathsf{spar}(f))$ for monotone and
symmetric Boolean functions. It will be interesting to find other class of
functions for which the upper bound can be improved. Our result that the
$\mathsf{mbs}$ vs. $\log(\mathsf{spar})$ question is equivalent to the
$\mathsf{s}$ vs. $\mathrm{deg}$ question, might give another direction to
attack this old open question.

This work also showed that the ratio
$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}$ is independent of the
iteration number $l$. Even though we were not able to use it to show
$\mathsf{fmbs}=O(\log(\mathsf{spar}(f))^{2})$, this results seems to be of
independent interest in terms of behavior of these monotone measures.

Some of the other open questions from this work are listed below.

###### Open question 4.1

Can we prove that for any Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
$\mathsf{fmbs}(f)=O(\log(\mathsf{spar}(f))^{2})$?

Another possible open question in this direction is asking about best possible
separation between $\mathsf{fmbs}$ and $\log(\mathsf{spar})$. Right now it is
known that for all Boolean function
$\mathsf{fmbs}(f)=O(\log(\mathsf{spar}(f))^{4})$ and the best known separation
is due to Kushilevitz (described in [17]), giving a function $f$ such that
$\mathsf{s}(f)=\Omega(\mathrm{deg}(f)^{1.63})$. Can we give a better
separation for monotone measures?

###### Open question 4.2

Does there exist a function $f$ for which,
$\mathsf{fmbs}(f)=\Omega(\log(\mathsf{spar}(f))^{\alpha})$ for some
$\alpha>1.63$?

## References

  * [1] Scott Aaronson.  Quantum certificate complexity.  CoRR, quant-ph/0210020, 2002.  URL: http://arxiv.org/abs/quant-ph/0210020.
  * [2] Scott Aaronson, Shalev Ben-David, and Robin Kothari.  Separations in query complexity using cheat sheets.  In STOC, pages 863–876, 2016.  doi:10.1145/2897518.2897644.
  * [3] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal.  Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem.  In STOC, pages 1330–1342, 2021.  doi:10.1145/3406325.3451047.
  * [4] Shalev Ben-David and Eric Blais.  A tight composition theorem for the randomized query complexity of partial functions: Extended abstract.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 240–246. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00031.
  * [5] Harry Buhrman and Ronald de Wolf.  Communication complexity lower bounds by polynomials.  In Proceedings 16th Annual IEEE Conference on Computational Complexity, pages 120–130. IEEE, 2001.
  * [6] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  doi:10.1016/S0304-3975(01)00144-X.
  * [7] Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny.  Certificate games.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 32:1–32:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.ITCS.2023.32.
  * [8] Justin Gilmer, Michael E. Saks, and Srikanth Srinivasan.  Composition limits and separating examples for some Boolean function complexity measures.  Combinatorica, 36(3):265–311, 2016.  doi:10.1007/s00493-014-3189-x.
  * [9] Hao Huang.  Induced subgraphs of hypercubes and a proof of the sensitivity conjecture.  Annals of Mathematics, 190(3):949–955, 2019.  doi:10.4007/annals.2019.190.3.6.
  * [10] Rahul Jain and Hartmut Klauck.  The partition bound for classical communication complexity and query complexity.  In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 247–258. IEEE Computer Society, 2010.  doi:10.1109/CCC.2010.31.
  * [11] Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan.  Log-rank and lifting for and-functions.  In STOC, volume 53, pages 197–208, 2021.
  * [12] Raghav Kulkarni and Avishay Tal.  On fractional block sensitivity.  Chicago J. Theor. Comput. Sci, 8:1–16, 2016.
  * [13] Raghav Kulkarni and Avishay Tal.  On fractional block sensitivity.  Chic. J. Theor. Comput. Sci., 2016, 2016.  URL: http://cjtcs.cs.uchicago.edu/articles/2016/8/contents.html.
  * [14] Bruno Loff and Sagnik Mukhopadhyay.  Lifting theorems for equality.  In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 50:1–50:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL: https://doi.org/10.4230/LIPIcs.STACS.2019.50, doi:10.4230/LIPICS.STACS.2019.50.
  * [15] Gatis Midrijanis.  Exact quantum query complexity for total boolean functions.  arXiv preprint quant-ph/0403168, 2004.
  * [16] Noam Nisan and Mario Szegedy.  On the degree of Boolean functions as real polynomials.  Computational Complexity, 4:301–313, 1994.  doi:10.1007/BF01263419.
  * [17] Noam Nisan and Avi Wigderson.  On rank vs. communication complexity.  Combinatorica, 15(4):557–565, 1995.  doi:10.1007/BF01192527.
  * [18] Ryan O’Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, and Yu Zhao.  A composition theorem for parity kill number.  In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 144–154. IEEE Computer Society, 2014.  doi:10.1109/CCC.2014.22.
  * [19] Avishay Tal.  Properties and applications of Boolean function composition.  In ITCS, pages 441–454, 2013.  doi:10.1145/2422436.2422485.

##  Appendix 0.A Proof of Theorem 1.1 and 1

######  Proof (Proof of Theorem 1.1)

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is monotone then $f^{l}$ is also
monotone. Hence from Theorem 1.3 it follows that
$\mathsf{mbs}(f^{l})=\mathsf{MCC}(f^{l})$ which gives
$\mathsf{mbs}(f^{l})=\mathsf{fmbs}(f^{l})$.

Now we consider $f$ to be a non-monotone Boolean function. We consider two sub
cases $\mathsf{mbs}(f)=1$ and $\mathsf{mbs}(f)\geq 2$ separately. The sub case
of $f$ being non-monotone with $\mathsf{mbs}(f)=1$ does not arise in the proof
of $\mathsf{fbs}$ and $\mathsf{bs}$ ratio. This is because $\mathsf{bs}(f)\geq
2$ for every non-monotone function $f$.

If $\mathsf{mbs}(f)=1$ and if $\mathsf{mbs}(f^{l})=1$ for all $l\geq 1$ then
using the fact that $\mathsf{fmbs}(f)=O(\mathsf{mbs}^{2}(f))$ we get
$\mathsf{fmbs}(f^{l})/\mathsf{mbs}(f^{l})=O(1)$. If the aforementioned
condition does not hold i.e. there exists a $k\in\mathbb{N}$ s.t.
$\mathsf{mbs}(f^{k})\geq 2$ then what remains to show is that
$\mathsf{fmbs}(f^{l})/\mathsf{mbs}(f^{l})\leq p(n)$ for all $l\geq k$. It
follows that the argument for this part is similar to the case when $f$ is non
monotone and $\mathsf{mbs}(f)\geq 2$.

To prove the theorem for non-monotone functions and $\mathsf{mbs}(f)\geq 2$,
we will need several lemmas about the behaviour of these monotone complexity
measures under composition.

######  Lemma 1 ([19])

For Boolean functions $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$, if $f(z^{n})=g(z^{m})=z$ for
$z\in\\{0,1\\}$ then:

$\mathsf{fbs}(f\circ g,z^{nm})\geq\mathsf{fbs}(f,z^{n})\mathsf{fbs}(g,z^{m}).$

The above observation can be adapted to $\mathsf{fmbs}^{0}$.

###### Lemma 2

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ are Boolean functions with
$\mathsf{fmbs}^{0}(f)=\mathsf{fmbs}(f,x)$ and
$\mathsf{fmbs}^{0}(g)=\mathsf{fmbs}(g,y)$ then:

$\mathsf{fmbs}^{0}(f\circ g)\geq\mathsf{fmbs}^{0}(f)\mathsf{fmbs}^{0}(g).$

###### Proof

Consider the inputs $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{m}$ s.t.
$\mathsf{fmbs}^{0}(f)=\mathsf{fmbs}(f,x)$ and
$\mathsf{fmbs}^{0}(g)=\mathsf{fmbs}(g,y)$. As
$f_{x}(0^{n-|x|})=g_{y}(0^{n-|y|})=0$ hence by 1 it follows that:

$\mathsf{fmbs}(f_{x}\circ
g_{y},\boldsymbol{0})\geq\mathsf{fmbs}^{0}(f)\mathsf{fmbs}^{0}(g),$

where $\boldsymbol{0}$ is the all zero string in $\\{0,1\\}^{(n-|x|)(n-|y|)}$.

Fix any $z\in g^{-1}(1)$. (If $g$ is the constant $0$ function, then the lemma
holds since $\mathsf{fmbs}^{0}(g)=0$.) Now, consider the input
$\gamma:=(\gamma_{1},\gamma_{2},...,\gamma_{m})$ with
$\gamma_{1},...,\gamma_{n}\in\\{0,1\\}^{m}$ defined as:

$\gamma_{i}:=\begin{cases}&z,\;if\;x_{i}=1\\\ &y,\;otherwise\end{cases}$

Observe that $\mathsf{fmbs}(f\circ g,\gamma)\geq\mathsf{fmbs}(f_{x}\circ
g_{y},\boldsymbol{0})$, hence giving us the result:

$\mathsf{fmbs}^{0}(f\circ g)\geq\mathsf{fmbs}^{0}(f)\mathsf{fmbs}^{0}(g).$

The remaining lemmas given below are proved in the Appendix 0.B.

###### Lemma 3

Let $f,g$ be two Boolean function where $f$ is non-monotone and
$z\in\\{0,1\\}$ then,
1\. $\mathsf{mbs}^{z}(f\circ g)\geq\mathsf{mbs}(g)$,
2\. $\mathsf{fmbs}^{z}(f\circ g)\geq\mathsf{fmbs}(g)$.

###### Lemma 4

For Boolean functions $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ we have:

$\mathsf{mbs}^{z}(f\circ
g)\geq\max\\{\mathsf{mbs}^{z}(f)\mathsf{mbs}^{0}(g),\mathsf{bs}^{z}(f)\min\\{\mathsf{mbs}^{0}(g),\mathsf{mbs}^{1}(g)\\}\\}.$

###### Corollary 2

Let $f$ be a non-monotone Boolean function with $z\in\\{0,1\\}$ then, the
sequence $\\{\mathsf{mbs}^{z}(f^{l})\\}_{l\in\mathbb{N}}$ is monotone
increasing and if $\mathsf{mbs}(f)\geq 2$ then for every $z\in\\{0,1\\}$ the
sequence $\\{\mathsf{mbs}^{z}(f^{l})\\}_{l\in\mathbb{N}}$ tends to infinity.

We are now in a position to prove Theorem 1.1. To recall, Theorem 1.1 states
that for any function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ the ratio
$\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}$ is independent of $l$.

Remember that we are left with the case when $f$ is not monotone and
$\mathsf{mbs}(f)\geq 2$. If we show that there exists a sequence
$\\{r_{l}\\}_{l\geq 1}$ s.t. for all $l\geq 1$ we have:

$\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}\geq r_{l}\geq 1/p(n),$

then we will be done.

Now consider the sequence:

$r_{l}:=\min\\{r^{0}_{l},\;r^{1}_{l}\\},$

where $r^{z}_{l}:=\frac{\mathsf{mbs}^{z}(f^{l})}{\mathsf{fmbs}^{z}(f^{l})}$
for $z\in\\{0,1\\}$. Taking $z^{\prime}\in\\{0,1\\}$ as
$\mathsf{fmbs}(f^{l})=\mathsf{fmbs}^{z^{\prime}}(f^{l})$, we get:

$\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}=\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}^{z^{\prime}}(f^{l})}\geq\frac{\mathsf{mbs}^{z^{\prime}}(f^{l})}{\mathsf{fmbs}^{z^{\prime}}(f^{l})}=r_{l}^{z^{\prime}}\geq
r_{l},$

i.e. $\frac{\mathsf{mbs}(f^{l})}{\mathsf{fmbs}(f^{l})}$ has $r_{l}$ as its
lower bound. What remains to show is that for all $l\geq 1$:

$r_{l}\geq 1/p(n).$

Now, notice it is sufficient to show that for $l\geq l_{0}$, $r_{l}\geq
1/p(n),$ where $l_{0}$ is a parameter we fix later.

To this effect, we show that for $l\geq l_{0}$:

$r_{l+1}\geq r_{l}(1-2^{-1-\lfloor\frac{l-(l_{0}+1)}{2}\rfloor}).$ (2)

Equation 2 will complete the proof because it implies that for all $s\geq
l_{0}$:

$r_{s}\geq
r_{l_{0}}\cdot\prod_{i=1}^{\infty}(1-2^{-i})^{2}\underset{\autoref{ineq}}{\geq}r_{l_{0}}\cdot
1/e^{4}\geq 1/e^{4}\cdot q(n),$

where $q(n)$ is any function of $n$ s.t. $r_{l_{0}}\geq q(n)$.

For the rest of the proof, our aim will be to show Equation 2. We do this by
rounding a solution of the linear program for $\mathsf{fmbs}(f^{l+1})$ to a
feasible solution for the integer program corresponding to
$\mathsf{mbs}(f^{l+1})$. To accomplish this goal, we look at the composed
function $f^{l+1}$ as $f\circ f^{l}$, which seems natural given the fact that
we have a better understanding of the function $f$.

Let $x:=(x^{1},x^{2},...,x^{n})\in\\{0,1\\}^{n^{l+1}}$ be an input for which
$\mathsf{fmbs}^{z}(f^{l+1})=\mathsf{fmbs}(f^{l+1},x)$ where
$x^{1},x^{2},...,x^{n}\in\\{0,1\\}^{n^{l}}$ and let $y\in\\{0,1\\}^{n}$ be the
$n$-bit string corresponding to $x$
i.e.$\;\forall\;i\in[n],\;y_{i}:=f^{l}(x^{i})$. As already mentioned, we will
convert the optimal solution $x$ for $\mathsf{fmbs}(f^{l+1})$ to a feasible
solution $\widehat{x}$ (mentioned later) for $\mathsf{mbs}(f^{l+1})$.

Let $\\{B_{1},...,B_{k}\\}$ be the set of all minimal sensitive blocks for
$y$. What now needs to be observed is that any minimal monotone sensitive
block for $f^{l+1}$ corresponds to a minimal sensitive block $B_{i}$ for $f$.
The consequence of this observation is that every feasible solution of
$\mathsf{fmbs}(f^{l+1})$ is a feasible solution of the following linear
program:

$\max\sum_{i=1}^{k}w_{i},$

s.t.

$\sum_{j:i\in B_{j}}w_{j}\leq\mathsf{fmbs}(f^{l},x^{i}),\;\forall\;i\in[n],$
$w_{j}\geq 0,\forall j\in[k].$

We now convert an optimal solution of $\mathsf{fmbs}(f^{l+1})$ to a feasible
solution of $\mathsf{mbs}(f^{l+1})$. Let $\\{w^{*}_{j}\\}_{j\in[k]}$ be an
optimal assignment of weights for the above linear program and let
$w^{{}^{\prime}}_{j}:=\lfloor w_{j}^{*}\cdot r_{l}\rfloor$. Define
$\widehat{x}:=(\widehat{x}^{1},\widehat{x}^{2},...,\widehat{x}^{n}),$ where
$\mathsf{mbs}(f^{l},\widehat{x}^{i}):=\mathsf{mbs}^{y_{i}}(f^{l})$. It can be
observed that for all $j\in[k]$ we have:

$\sum_{j:i\in B_{j}}w^{{}^{\prime}}_{j}\leq\sum_{j:i\in B_{j}}w^{*}_{j}\cdot
r_{l}\leq\mathsf{fmbs}(f^{l},x^{i})r_{l}\leq\mathsf{fmbs}(f^{l},x^{i})\cdot\frac{\mathsf{mbs}^{y_{i}}(f^{l})}{\mathsf{fmbs}^{y_{i}}(f^{l})}\leq\mathsf{mbs}(f^{l},\widehat{x}^{i}),$

where the last inequality follows from the fact that
$f^{l}(x^{i})=f^{l}(\widehat{x}^{i})=y_{i}$.

Now consider the following integer program:

$\max\sum_{i=1}^{k}w_{i},$

s.t.

$\sum_{j:i\in
B_{j}}w_{j}\leq\mathsf{mbs}(f^{l},\widehat{x}^{i}),\;\forall\;i\in[n],$
$w_{j}\in\\{0,1,2,\dots,\mathsf{mbs}(f^{l})\\},\forall j\in[k].$

Clearly, $w^{{}^{\prime}}$ forms a feasible solution for the above mentioned
integer linear program.

We claim that using the assignment $w^{{}^{\prime}}_{i}$ defined above we can
construct $\sum_{i=1}^{k}w^{{}^{\prime}}_{i}$ many disjoint monotone sensitive
blocks for $\widehat{x}$, which would imply
$\sum_{i=1}^{k}w^{{}^{\prime}}_{i}\leq\mathsf{mbs}(f^{l+1},\widehat{x})$.

We argue this as follows, consider the minimal monotone sensitive block
$B_{1}$ for $y$ and to simplify the discussion assume that
$B_{1}:=\\{i_{1},\;i_{2}\\}$. Now pick the $i_{1}^{th}$ copy of $f^{l}$.
Consider $w^{{}^{\prime}}_{1}$ many disjoint monotone blocks for $x^{i_{1}}$
and denote them by
$B^{{1}}_{i_{1},1},\;B^{{1}}_{i_{1},2},...\;,B^{1}_{i_{1},w^{{}^{\prime}}_{1}}$.
Similarly consider $w^{{}^{\prime}}_{1}$ many disjoint monotone sensitive
blocks for $x^{i_{2}}$. Observe that each of the monotone blocks
$B^{1}_{i_{1},1}\cup B^{1}_{i_{2},{1}},\;B^{1}_{i_{1},{2}}\cup
B^{1}_{i_{2},2},...,\;B^{1}_{i_{1},w^{{}^{\prime}}_{1}}\cup
B^{1}_{i_{2},w^{{}^{\prime}}_{1}}$ are sensitive for the input $\widehat{x}$
and are pairwise disjoint.

This implies:

$\mathsf{fmbs}^{z}(f^{l+1})r_{l}\leq\sum_{i=1}^{k}w_{i}^{*}r_{l}\leq\sum_{i=1}^{k}(w^{{}^{\prime}}_{i}+1)\leq\mathsf{mbs}(f^{l+1},\widehat{x})+2^{n}\leq\mathsf{mbs}^{z}(f^{l+1})+2^{n},$

where the last inequality follows from the fact that $f^{l+1}(\widehat{x})=z$
and by the fact that monotone blocks for $y$ are subsets of $[n]$.

Using the aforementioned inequality, we get:

$\displaystyle r^{z}_{l+1}$
$\displaystyle=\frac{\mathsf{mbs}^{z}(f^{l+1})}{\mathsf{fmbs}^{z}(f^{l+1})}\geq
r_{l}-\frac{2^{n}}{\mathsf{fmbs}^{z}(f^{l+1})}$
$\displaystyle=r_{l}\bigg{(}1-\frac{2^{n}}{\mathsf{fmbs}^{z}(f^{l+1})}\cdot\frac{\mathsf{fmbs}^{z^{{}^{\prime}}}(f^{l})}{\mathsf{mbs}^{z^{{}^{\prime}}}(f^{l})}\bigg{)}\underset{\autoref{mbs
and fmbs of
composition}}{\geq}r_{l}\bigg{(}1-\frac{2^{n}}{\mathsf{mbs}^{z^{{}^{\prime}}}(f^{l})}\bigg{)}$
(3)

where $z^{{}^{\prime}}=\underset{z\in\\{0,1\\}}{\arg\min}\;r^{z}_{l}$.

We fix $l_{0}$ to be the minimum integer s.t. $\mathsf{mbs}(f^{l_{0}})\geq
2.2^{n}$. This gives us:

$\displaystyle\mathsf{mbs}^{z^{{}^{\prime}}}(f^{l})$
$\displaystyle\underset{\autoref{monotonicity under
composition}}{\geq}\mathsf{mbs}^{z^{{}^{\prime}}}(f^{l-(l_{0}+1)})\cdot\underset{b\in\\{0,1\\}}{\min}\;{\mathsf{mbs}^{b}(f^{l_{0}+1})}$
$\displaystyle\underset{\autoref{lemma: fmbs monotone
increasing}}{\geq}2^{\lfloor\frac{l-(l_{0}+1)}{2}\rfloor}\cdot(2\cdot 2^{n}).$

Putting the value of $\mathsf{mbs}^{z^{{}^{\prime}}}(f^{l})$ in Appendix 0.A
gives us Equation 2, completing the proof.

######  Proof (Proof of 1)

We will derive the lifting for $\mathsf{fmbs}$ by using a lifting for
$\mathsf{fmbs}^{0}$. Formally, if $\mathsf{mbs}(f)=O(M(f)^{\alpha})$, where
the complexity measure $M(.)$ composes, then
$\mathsf{fmbs}^{0}(f)=M(f)^{\alpha}$.

Let $\mathsf{fmbs}^{0}(f)>M(f)^{\alpha}$ i.e.
$\mathsf{fmbs}^{0}(f)=M(f)^{\alpha}+\epsilon$ for some $\epsilon>0$. This
implies,

$\displaystyle\mathsf{fmbs}^{0}(f)^{l}=$
$\displaystyle(M(f)^{\alpha})^{l}(1+\epsilon^{{}^{\prime}})^{l},$ where
$\epsilon^{{}^{\prime}}:=\epsilon/M(f)^{\alpha}$,
$\displaystyle\mathsf{fmbs}^{0}(f^{l})\geq\mathsf{fmbs}^{0}(f)^{l}$
$\displaystyle\geq(M(f)^{\alpha})^{l}(1+\epsilon^{{}^{\prime}})^{l}.$ Using 2
and Theorem 1.1, we get: $\displaystyle p(n)M(f^{l})^{\alpha}\geq
p(n)\mathsf{mbs}(f^{l})$ $\displaystyle\geq\mathsf{fmbs}^{0}(f^{l})\geq
M(f)^{l\alpha}(1+\epsilon^{{}^{\prime}})^{l}.$ This implies, $\displaystyle
p(n)$ $\displaystyle\geq(1+\epsilon^{{}^{\prime}})^{l}$

Which is a contradiction for a fixed $n$ and a sufficiently large $l$.

Now using the above lifting for $\mathsf{fmbs}^{0}(f)$ we derive the lifting
for $\mathsf{fmbs}(f)$.

Let $\mathsf{fmbs}(f)>M(f)^{2\alpha}$ i.e.
$\mathsf{fmbs}(f)=M(f)^{2\alpha}+\epsilon$ for some $\epsilon>0$. This
implies,

$\displaystyle\mathsf{fmbs}(f)^{l}=$
$\displaystyle(M(f)^{2\alpha})^{l}(1+\epsilon^{{}^{\prime}})^{l},$ where
$\epsilon^{{}^{\prime}}:=\epsilon/M(f)^{2\alpha}$. Now by 3 it follows that:
$\displaystyle\mathsf{fmbs}^{0}(f^{2})^{l}\geq\mathsf{fmbs}(f)^{l}$
$\displaystyle\geq(M(f)^{2\alpha})^{l}(1+\epsilon^{{}^{\prime}})^{l}.$ Using 2
and Theorem 1.1, we get: $\displaystyle p(n)M(f)^{2l\alpha}\geq
p(n)M(f^{2l})^{\alpha}\geq p(n)\mathsf{mbs}(f^{2l})$
$\displaystyle\geq\mathsf{fmbs}^{0}(f^{2l})\geq\mathsf{fmbs}(f)^{l}\geq
M(f)^{2l\alpha}(1+\epsilon^{{}^{\prime}})^{l}.$ This implies, $\displaystyle
p(n)$ $\displaystyle\geq(1+\epsilon^{{}^{\prime}})^{l}$

Which is a contradiction for a fixed $n$ and a sufficiently large $l$.

Now, if the complexity measure $M$ satisfies the condition $M(1-f)=O(M(f))$
then using the fact that $\mathsf{fmbs}^{1}(f)=\mathsf{fmbs}^{0}(1-f)$, we
have:

$\mathsf{fmbs}(f)=\max\\{\mathsf{fmbs}^{0}(f),\;\mathsf{fmbs}^{1}(f)\\}=O(M(f)^{\alpha}).$

##  Appendix 0.B Results needed for the proof of Theorem 1.1

We basically give an analog of the identities that hold for standard
complexity measures for monotone complexity measures presented in [19]. We
start by showing how $\mathsf{MCC}(f)$ and $\mathsf{mbs}(f)$ are related.

###### Theorem 0.B.1

For a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ we have:

$\mathsf{MCC}^{z}(f)\leq\mathsf{mbs}^{z}(f)\mathsf{ms}^{1-z}(\widetilde{f}),$

where $\widetilde{f}(x):=f(1-x_{1},1-x_{2},...,1-x_{n})$.

###### Proof

Let $\mathsf{MCC}(f)=\mathsf{MCC}(f,x)$. We now consider the function $f_{x}$
at the input $0^{n-|x|}$ along with a set of disjoint minimal sensitive blocks
$\\{B_{1},B_{2},...,B_{k}\\}$ with $k=\mathsf{mbs}(f,x)$. We claim that for
every $i\in[k]$, $f_{x}$ is sensitive on $0^{\oplus{B_{i}}}$ at each index
$j\in B_{i}$. If this was not the case then there would exist $B\subsetneq
B_{i}$ s.t. $B$ is a sensitive block for $f_{x}$ at $0^{n-|x|}$, contradicting
the claim that $B_{i}$ is minimal.

Now, we claim that the set $\cup_{i\in[k]}{B_{i}}$ is a certificate for
$f_{x}$ at $0^{n-|x|}$. If this was not the case then we would have obtained a
sensitive block $B$ at $0^{n-|x|}$ s.t. $B\cap B_{i}=\emptyset$ for all
$i\in[k]$. This would have contradicted the assumption that
$\\{B_{i}:i\in[k]\\}$ is a witness for $\mathsf{mbs}(f,x)$. Hence from the
above discussion we obtain:

$\mathsf{MCC}(f)=\mathsf{MCC}(f,x)\leq\sum_{i\in[k]}|B_{i}|\leq\mathsf{mbs}(f,x)\mathsf{ms}(\widetilde{f})\leq\mathsf{mbs}(f)\mathsf{ms}(\widetilde{f}).$

In the following theorem we show that the composition result for Boolean
functions $f,g$ (see [19]), can also be extended to $\mathsf{mbs}$.

###### Theorem 0.B.2

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $g:\\{0,1\\}^{m}\to\\{0,1\\}$ be Boolean
functions then $\mathsf{mbs}(f\circ g)\leq\mathsf{fbs}(f).\mathsf{mbs}(g)$.

###### Proof

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be two Boolean functions. Now consider
an input $(x^{1},x^{2},...,x^{n})\in(\\{0,1\\}^{m})^{n}$ where
$x^{i}:=(x^{i}_{1},...,x^{i}_{m})$ for $i\in[n]$.

Now we wish to calculate $\mathsf{mbs}(f\circ g,x)$. Any minimal monotone
block for $f\circ g$ at $x$ is a union of minimal monotone blocks for
different $g^{i}$ where $i\in\mathcal{I}\subseteq[n]$ where $\mathcal{I}$ is a
minimal sensitive block for $f$ at $y:=(g(x^{1}),..,g(x^{n}))$.

If we assume that $\mathcal{B}_{1},..,\mathcal{B}_{k}$ is the set of all
minimal sensitive blocks for $f$ at $y$ and by $m_{j}$ let us denote the
number of minimal monotone sensitive blocks for $f\circ g$ that intersects
with $\mathcal{B}_{j}$. As we want to obtain a collection of disjoint monotone
sensitive blocks for $f\circ g$ at $x$ hence we have that $\forall
i\in[n],\;\sum_{j:i\in\mathcal{B}_{j}}m_{j}\leq\mathsf{mbs}(g,x^{i}).$ Hence
$\mathsf{mbs}(f\circ g,x)$ is equal to the optimal value of the following
integer program:

$\max\sum_{i=1}^{k}m_{i},$

s.t.

$\sum_{j:i\in\mathcal{B}_{j}}m_{j}\leq\mathsf{mbs}(g,x^{i}),\;\forall
i\in[n],$ $m_{i}\in\\{0,1,..,\mathsf{mbs}(g)\\}$

Now, relaxing the above integer program to linear program we get a feasible
solution for the linear program corresponding to $\mathsf{fbs}(f,y)$ by simply
dividing it by $\mathsf{mbs}(g)$.: This implies,

$\mathsf{fbs}(f,y)\geq\frac{OPT(LP(\mathsf{mbs}(f\circ
g,x)))}{\mathsf{mbs}(g)}\geq\frac{OPT(IP(\mathsf{mbs}(f\circ
g,x)))}{\mathsf{mbs}(g)}=\frac{\mathsf{mbs}(f\circ g,x)}{\mathsf{mbs}(g)}$

Taking $x$ to be the input s.t. $\mathsf{mbs}(f\circ g)=\mathsf{mbs}(f\circ
g,x)$ then we get our desired result.

The next lemma shows that how

######  Proof (Proof of 3)

1\. Let $\mathsf{mbs}(g)=\mathsf{mbs}(g,x)$ and assume that $g(x)=0$. Now as
we know that $f$ is non-monotone hence there exists inputs
$x^{1},x^{2},x^{3},x^{4}$ s.t. $x^{1}<x^{2}$ and $x^{3}<x^{4}$ and
$f(x^{1})\neq f(x^{2})$ and $f(x^{3})\neq f(x^{4})$. In fact we can consider
the stronger assumption $|x^{1}-x^{2}|=|x^{3}-x^{4}|=1$ i.e. have hamming
distance 1.

For ease of discussion let us assume $f(x^{1})=f(x^{4})=0$ and
$f(x^{2})=f(x^{3})=1$.

Now consider inputs $y^{i}\equiv(y^{i}_{1},...,y^{i}_{n})$,
$i\in\\{1,2,3,4\\}$, for $f\circ g$ which are defined as follows:

$y^{i}_{j}:=\begin{cases}x&\text{, if $x^{i}_{j}=0$}\\\ \alpha&\text{,
o.w.}\end{cases},$

where $\alpha$ is any string in $g^{-1}(1)$.

What we claim is that $\mathsf{mbs}(f\circ g,y^{1})\geq\mathsf{mbs}(g)$. This
is because we can convert the string $x^{1}$ to $x^{2}$ by flipping the
corresponding bits in $y^{1}$. As $f\circ g(y^{1})=f(x^{1})=0$ hence we have
$\mathsf{mbs}^{0}(f\circ g)\geq\mathsf{mbs}(f\circ
g,y^{1})\geq\mathsf{mbs}(g).$ Similarly, we can convert the string $x^{3}$ to
$x^{4}$ by flipping the corresponding bits in $y^{3}$ to obtain
$\mathsf{mbs}^{1}(f\circ g)\geq\mathsf{mbs}(f\circ
g,y^{3})\geq\mathsf{mbs}(g)$.

If it was the case that $g(x)=1$ then the definition of $y^{i}$ for
$i\in\\{1,\;2,\;3,\;4\\}$ would have been as follows:

$y^{i}_{j}:=\begin{cases}x&\text{, if $x^{i}_{j}=1$}\\\ \alpha&\text{,
o.w.}\end{cases},$

where $\alpha$ is any string in $g^{-1}(0)$. Using a similar argument as done
for the case when $g(x)=0$ we would have obtained the same inequality.

2\. Let $\mathsf{fmbs}(f)=\mathsf{fmbs}(f,x)$ and let $g(x)=0$. Let
$x^{1},x^{2},x^{3},x^{4}\in\\{0,1\\}^{n}$ and
$y^{1},y^{2},y^{3},y^{4}\in(\\{0,1\\}^{n})^{m}$ be the strings defined in part
1.

Now consider the linear program for $\mathsf{fmbs}(f\circ g,y^{1})$ i.e.:

$\mathsf{fmbs}(f\circ g,y^{1}):=\sum_{w\in\mathcal{W}(f\circ g)}b_{w},$

s.t.

$\forall(i,j)\in[n]\times[m],\sum_{w\in\mathcal{W}(f\circ g,y^{1}):(i,j)\in
w}b_{w}$

and,

$\forall w\in\mathcal{W}(f\circ g,y^{1}),\;b_{w}\in[0,1].$

Now, as $|x^{1}-x^{2}|=1$ hence let us consider the copy of $g$ in $f\circ g$,
call it $j\in[n]$, which corresponds to the bit where $x^{1}$ and $x^{2}$
differ. As $f(x^{1})\neq f(x^{2})$ and $|x^{2}-x^{1}|=1$ hence all the
monotone blocks for the $j-th$ copy of $g$ are monotone blocks for $f\circ g$.
Now, let
$\\{\widehat{b}_{w^{{}^{\prime}}}:w^{{}^{\prime}}\in\mathcal{W}(g,x)\\}$ be a
feasible solution corresponding to the linear program for
$\mathsf{fmbs}(g,x)$.

Consider the following assignment to weights $b_{w}$:

$b_{w}:=\begin{cases}&\widehat{b}_{w},\text{ if w$\in\mathcal{W}(g,x)$}\\\
&0,\text{ otherwise}\end{cases}$

It is easy to verify that that the above assignment for $b_{w}$ forms a
feasible solution for the LP corresponding to $\mathsf{fmbs}(f\circ g,y^{1})$.
Hence

$\mathsf{fmbs}^{0}(f\circ g)\geq\mathsf{fmbs}(f\circ
g,y^{1})\geq\mathsf{fmbs}(g).$

Similarly, we can say that:

$\mathsf{fmbs}^{1}(f\circ g)\geq\mathsf{fmbs}(f\circ
g,y^{3})\geq\mathsf{fmbs}(g).$

######  Proof (Proof of 4)

Let $p^{0},p^{1}$ be the inputs for which
$\mathsf{mbs}^{z}(g)=\mathsf{mbs}(g,p^{z}),$ for $z\in\\{0,1\\}$. Let
$\mathsf{mbs}^{z}(f)=\mathsf{mbs}(f,y)$. Now consider the input
$x\equiv(x^{1},x^{2},...,x^{n})$ defined as:

$x^{i}:=p^{y_{i}}.$

The $\mathsf{mbs}^{z}(f\circ g,x)$ is clearly
$\geq\mathsf{mbs}^{z}(f)\mathsf{mbs}^{0}(g)$. This is because for every
disjoint monotone sensitive block corresponding to $\mathsf{mbs}^{z}(f)$ we
have $\mathsf{mbs}^{0}(g)$ many disjoint sensitive blocks.

Similarly, for every disjoint sensitive block corresponding to
$\mathsf{bs}^{z}(f)$, we have
$\min\\{\mathsf{mbs}^{0}(g),\mathsf{mbs}^{1}(g)\\}$ many monotone sensitive
blocks. This gives $\mathsf{mbs}^{z}(f\circ
g)\geq\mathsf{bs}^{z}(f)\min\\{\mathsf{mbs}^{0}(g),\mathsf{mbs}^{1}(g)\\}$.

######  Proof (Proof of 2)

The monotone increasing part of the lemma is obtained using part 1 of 3 as
follows:

$\displaystyle\mathsf{mbs}^{z}(f^{l})\geq\mathsf{mbs}(f^{l-1})\geq\mathsf{mbs}^{z}(f^{l-1}).$

Now we show that the sequence diverges if $\mathsf{mbs}(f)\geq 2$. In
particular, we show that for all $l\geq 2$ and for all $z\in\\{0,1\\}$, we
have:

$\mathsf{mbs}^{z}(f^{l})\geq 2^{\lfloor l/2\rfloor}.$

We prove it via induction on $l$. The base case is for $l=2$. Using 4 and the
assumption that $\mathsf{mbs}(f)\geq 2$ we obtain:

$\mathsf{mbs}^{z}(f^{2})\geq\mathsf{mbs}(f)\geq 2$

Now for the inductive step consider $l=k$. Using part 1 of 3 and we get,

$\mathsf{mbs}^{z}(f^{k})\geq\mathsf{mbs}^{z}((f^{2})^{\lfloor
k/2\rfloor})\geq\mathsf{mbs}^{z}(f^{2})\mathsf{mbs}^{0}(f^{{2\lfloor
k/2\rfloor-2}}).$

Hence by using the induction hypothesis we get that:

$\mathsf{mbs}^{z}(f^{k})\geq\mathsf{mbs}^{z}(f^{2})\mathsf{mbs}^{0}(f^{{2\lfloor
k/2\rfloor-2}})\geq 2.2^{\lfloor k/2\rfloor-1}=2^{\lfloor k/2\rfloor}$

A natural question to ask at this point is do we have a relation for the ratio
between $\mathsf{MCC}(f^{l})$ and $\mathsf{mbs}(f^{l})$ similar to
$\mathsf{fmbs}(f^{l})$ and $\mathsf{mbs}(f^{l})$? That might be an interesting
problem to look at but what we do have is the following simple corollary which
follows from the fact that
$\mathsf{MCC}(f)=O(\mathsf{fmbs}(f)\log(\mathsf{spar}(f)))$.

###### Corollary 3

For a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ we have that for
all $l\geq 1$:

$\frac{\mathsf{MCC}(f^{l})}{\mathsf{mbs}(f^{l})\log(\mathsf{spar}(f^{l}))}\leq
C(n),$

where $C(n)$ is a function independent of $l$.

###### Proof

Using the fact that
$\mathsf{MCC}(f)=O(\mathsf{fmbs}(f)\log(\mathsf{spar}(f)))$ and by Theorem 1.1
we get:

$\frac{\mathsf{MCC}(f^{l})}{\mathsf{fmbs}(f^{l})\log(\mathsf{spar}(f^{l}))}\cdot\frac{\mathsf{fmbs}(f^{l})}{\mathsf{mbs}(f^{l})}\leq\frac{\mathsf{MCC}(f^{l})}{\mathsf{mbs}(f^{l})\log(\mathsf{spar}(f^{l}))}=O(p(n)).$

Another interesting observation from Theorem 1.1 is the following corollary.

###### Corollary 4

For any Boolean function $f$ and constant $c>0$, there exists a
$l_{0}\in\mathbb{N}$ such that for all $l\geq l_{0}$,

$\mathsf{fmbs}(f^{l})\leq\mathsf{mbs}^{1+c}(f^{l}).$

###### Proof

Let us assume that no such $l_{0}$ exists i.e. there exists an infinite
sequence of integers, say $\\{m_{i}\\}_{i\geq 1}$ s.t.:

$\mathsf{fmbs}(f^{m_{i}})>\mathsf{mbs}(f^{m_{i}})\mathsf{mbs}^{c}(f^{m_{i}}),$

for all $i\geq 1$.

In other words, this implies that:

$p(n)\geq\frac{\mathsf{fmbs}(f^{m_{i}})}{\mathsf{mbs}(f^{m_{i}})}>\mathsf{mbs}^{c}(f^{m_{i}}),$

for all $i\geq 1$.

This is a contradiction to the fact that the sequence
$\\{\mathsf{mbs}(f^{l})\\}$ diverges.

Finally, we also mention the following inequality which has been used in the
proof of Theorem 1.1:

###### Proposition 1

$\prod_{i=1}^{\infty}(1-2^{-i})\geq 1/e^{2}$

###### Proof

We prove the inequality by applying A.M-G.M. inequality on positive real nos.
$\\{a_{1},...,a_{N}\\}$ where $a_{i}:=\frac{1}{1-2^{-i}}$ followed by taking
the limit $N\rightarrow\infty$.

Applying A.M.-G.M. inequality on $\\{a_{1},...,a_{N}\\}$, we get:

$(a_{1}a_{2}...a_{N})^{1/N}\leq\frac{\sum_{i=1}^{N}a_{i}}{N}$

This implies,

$\bigg{(}\prod_{i=1}^{N}(1-2^{-i})^{-1}\bigg{)}^{1/N}\leq\frac{\sum_{i=1}^{N}\frac{2^{i}}{2^{i}-1}}{N}.$

Now simplifying the above inequality we obtain the following set of
inequalities:

$\displaystyle\bigg{(}\prod_{i=1}^{N}(1-2^{-i})^{-1}\bigg{)}^{1/N}$
$\displaystyle\leq 1+\frac{\sum_{i=1}^{N}2^{-(i-1)}}{N}$
$\displaystyle=1+\frac{2}{N}(1-2^{-N})\leq 1+2/N.$

This implies,

$\prod_{i=1}^{N}(1-2^{-i})^{-1}\leq(1+2/N)^{N}.$

Taking $N\rightarrow\infty$ we get the desired inequality.

###  0.B.1 Characterization of Boolean functions with $\mathsf{mbs}(f)=1$

In this section, we provide another noticeable difference in the behaviour of
$\mathsf{bs}$ and $\mathsf{mbs}$. We already know from [19] that for all non-
monotone functions $\mathsf{bs}(f)\geq 2$. Interestingly, the same is not true
for $\mathsf{mbs}$ i.e. there are non-monotone Boolean functions for which
$\mathsf{mbs}(f)=1$. For example, the function:

$ODD-MAX-
BIT(X_{S_{1}},X_{S_{2}},...,X_{S_{k}}):=X_{S_{1}}-X_{S_{1}}X_{S_{2}}+X_{S_{1}}X_{S_{2}}X_{S_{3}}-...+(-1)^{k}\prod_{i=1}^{k}X_{S_{i}},$

where the product $X_{S}X_{T}:=X_{S\cap T}X_{S\setminus T\cup T\setminus S}$,
has $\mathsf{mbs}(f)=1$.

What we now show is that the $ODD-MAX-BIT$ is in fact the “only" function with
$\mathsf{mbs}(f)=1$. To prove the aforementioned result we need the following
claim about the structure of Boolean functions with $\mathsf{mbs}(f)\leq 1$.

###### Claim

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is a Boolean function with
$\mathsf{mbs}(f)=1$ and $f(0^{n})=0$ then there exists an input
$x\in\\{0,1\\}^{n}$ s.t. for all $y\in\\{0,1\\}^{n}$, if $y\ngeq x$ then
$f(y)=0$.

###### Proof

Consider a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with
$\mathsf{mbs}(f)=1$ and $f(0^{n})=0$ and let $k$ be the smallest integer s.t.
$f(x)=1$ and $|x|=k$. Now if we assume that there exists a $y\ngeq x$ with
$f(y)=1$ then we have $\mathsf{mbs}(f,x\wedge y)\geq 2$ which contradicts the
assumption of $\mathsf{mbs}(f)=1$.

###### Lemma 5

If $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is a Boolean function with
$\mathsf{mbs}(f)\leq 1$ then $f$ can be expressed as $ODD-MAX-
BIT(X_{S_{1}},X_{S_{2}},...,X_{S_{k}})$ or 1-($ODD-MAX-
BIT(X_{S_{1}},X_{S_{2}},...,X_{S_{k}}))$ where $X_{S_{i}}$ are monomials
corresponding to set $S_{i}\subseteq[n]$.

###### Proof

We prove the lemma by applying induction on the arity of the Boolean function
$f$ i.e. $n$. For the base case let $n=1$.

Now if $f$ is a constant function then $f(x)=X_{\phi}$ or $1-X_{\phi}$ where
$X_{\phi}=1$. If it is not then $f(x)=x_{1}$ or $1-x_{1}$. We see that the
condition is satisfied for the base case of $n=1$.

Now for the inductive step assume that $f(0^{n})=0$ with $n=k$ and
$\mathsf{mbs}(f)\leq 1$. Using subsection 0.B.1 we have that there exists a
$x\in\\{0,1\\}^{n}$ s.t. $f(x)=1$ and for all $y\ngeq x$ we have $f(y)=0$.
This implies,

$f(x)=X_{S}g(x),$

where $S:=supp(x)$ and $g:\\{0,1\\}^{n-|x|}\rightarrow\\{0,1\\}$ is the
restriction of $f$ on the support of $x$ i.e. $g:=f_{x}$. As $g$ is the
restriction of $f$ on $x$ hence $\mathsf{mbs}(g)\leq 1$. For the case when
$\mathsf{mbs}(g)=0$ i.e. $g$ is constant, we have $f(x)=0=1-X_{\phi}$ or
$f(x)=X_{S}$=$OMB(X_{S})$ for the case when $g(x)=0$ or $1$ respectively. This
implies we can assume $g$ to be a non-constant function i.e.
$\mathsf{mbs}(g)=1$. Now using the induction hypothesis we have:

$g(x)=X_{1}-X_{S_{1}}X_{S_{2}}+...+(-1)^{k}X_{S_{1}}X_{S_{2}}...X_{S_{k}}=OMB(X_{S_{1}},X_{S_{2}},...,X_{S_{k}}),$

for some $S_{1},...,S_{k}\subseteq[n]$. Note that over here we could have also
assumed that $g(x)=1-OMB(X_{S_{1}},...,X_{S_{k}})$

Hence $f(x)=X_{S\cup S_{1}}-X_{S\cup S_{1}}X_{S_{2}}+...+(-1)^{k}X_{S\cup
S_{1}}X_{S_{2}}...X_{S_{k}}=OMB(X_{S\cup S_{1}},X_{S_{2}},...,X_{S_{k}})$ .

##  Appendix 0.C Relation between $\mathsf{mbs}(f)$ and
$\log(\mathsf{spar}(f))$

Sensitivity $\mathsf{s}(f)$ and Fourier degree $\mathrm{deg}(f)$ are two very
well studied complexity measures on Boolean functions. Huang, in his landmark
result [9], explicitly proved $\mathrm{deg}(f)\leq s(f)^{2}$ to show
sensitivity is polynomially related to other complexity measures. In the other
direction, Nisan and Szegedy [16] showed that
$\mathsf{s}(f)\leq\mathrm{deg}(f)^{2}$ around thirty years ago (we still don’t
know if this relation is tight). The article [11] used this relation to show
$\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$. We show that improving upper
bound $\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$ is indeed equivalent to
improving the upper bound on degree in terms of sensitivity (a long standing
open question).

Recall that Theorem 1.2 states: suppose, there exists a constant $\alpha$ such
that for every Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
$\mathsf{mbs}(f)=O(\log^{\alpha}{\mathsf{spar}(f)})$. Then for every Boolean
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
$\mathsf{s}(f)=O(\mathrm{deg}^{\alpha}(f))$.

To prove Theorem 1.2, we will need the following known relation between
Fourier degree and Fourier sparsity (see e.g. the proof of Fact 5.1 in [18]).
A proof is included for completeness.

###### Claim

For $f:\\{-1,1\\}^{n}\rightarrow\\{-1,1\\}$, $\mathsf{spar}(f)\leq
4^{\mathrm{deg}(f)}$.

###### Proof

Let $f:\\{-1,1\\}^{n}\rightarrow\\{-1,1\\}$. Define
$g:\\{0,1\\}^{n}\rightarrow\\{-1,1\\}$ by
$g(x_{1},x_{2},\dots,x_{n})=f(1-2x_{1},1-2x_{2},\dots,1-2x_{n})$ (notice that
$\mathrm{deg}(g)=\mathrm{deg}(f)$).

Let $g(x)=\sum_{S\subseteq[n]}\alpha_{S}\prod_{i\in S}x_{i}$ be its polynomial
representation. Since $g$ is integer-valued, all $\alpha_{S}$’s are integers
222This can be seen by induction, using the fact that $\alpha_{S}$ is an
integer linear combination of $f(S)$ (where we interpret $S$ as its indicator
vector) and $\alpha_{T}$ for $T\subsetneq S$..

Using the polynomial representation of $g$,

$f(y)=g(\frac{1-y_{1}}{2},...,\frac{1-y_{n}}{2})=\sum_{S\subseteq[n]}\alpha_{S}\prod_{i\in
S}\bigg{(}\frac{1-y_{i}}{2}\bigg{)}.$

From this representation of $f$, every Fourier coefficient of $f$ is an
integer multiple of $1/2^{\mathrm{deg}(f)}$. Say
$\widehat{f}(S)=\beta_{S}/2^{\mathrm{deg}(f)}$ for some
$\beta_{S}\in\mathbb{Z}$. Using Parseval,
$\sum_{S\subseteq[n]}\beta_{S}^{2}=4^{\mathrm{deg}(f)}$. Since $\beta_{S}$’s
are integers, this implies that sparsity is at most $4^{\mathrm{deg}(f)}$.

###### Corollary 5

For $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, $\mathsf{spar}(g)\leq
8^{\mathrm{deg}(g)}$.

###### Proof

Let $f:\\{-1,1\\}^{n}\rightarrow\\{-1,1\\}$ be defined by
$f(x)~{}=~{}1-2g(\frac{1-x_{1}}{2},...,\frac{1-x_{n}}{2})$ similar to what was
done in the previous claim. This is equivalent to
$g(x_{1},...,x_{n})=(1-f(1-2x_{1},...,1-2x_{n}))/2$. By the above claim,

$\mathsf{spar}(g)\leq 2^{\mathrm{deg}(f)}\mathsf{spar}(f)\leq
8^{\mathrm{deg}(g)}.$

∎

Now we can prove Theorem 1.2.

######  Proof (Proof of Theorem 1.2)

Let $w\in\\{0,1\\}^{n}$ be such that $\mathsf{s}(f)=\mathsf{s}(f,w)$. Consider
the function $\widetilde{f}$ defined by

$\widetilde{f}(x):=f(x\oplus w),$

where $x\oplus w$ denotes the bitwise XOR of $x$ and $w$.

Observe that $\mathsf{s}(\widetilde{f},0^{n})=\mathsf{s}(f,w)$. Also,
$\mathrm{deg}(\widetilde{f})\leq\mathrm{deg}(f)$ since performing an affine
substitution cannot increase the degree.

Using the given condition,
$\mathsf{mbs}(\widetilde{f})=O(\log^{\alpha}{\mathsf{spar}(\widetilde{f})})$
and the fact
$\mathsf{mbs}(\widetilde{f},0)=\mathsf{bs}(\widetilde{f},0)\geq\mathsf{s}(\widetilde{f},0)=\mathsf{s}(f,w)$
it follows that
$\mathsf{s}(f)=O(\log^{\alpha}{\mathsf{spar}(\widetilde{f})})$. Finally, by 5
and $\mathrm{deg}(\widetilde{f})\leq\mathrm{deg}(f)$, we get
$\mathsf{s}(f)=O(\mathrm{deg}^{\alpha}(\widetilde{f}))=O(\mathrm{deg}^{\alpha}(f))$
as desired.

Hence improving the bound on $\mathsf{mbs}(f)$ in terms of
$\log(\mathsf{spar}(f))$ is equivalent to improving the upper bound on
$\mathsf{s}(f)$ in terms of $\mathrm{deg}(f)$. The other possible approach of
improving the bound on $D^{0-dt}(f)$ is to improve the upper bound on
$\mathsf{fmbs}(f)$ in terms of $\log(\mathsf{spar}(f))$.

It turns out that for the class of symmetric and monotone Boolean functions
$\mathsf{mbs}(f)=\mathsf{fmbs}(f)$ = $\mathsf{MCC}(f)$, giving a much better
upper bound on $\mathsf{fmbs}(f)$ in terms of sparsity of $f$.

##  Appendix 0.D Boolean functions with $\mathsf{ms}(f)=\mathsf{MCC}(f)$

In this section, we look at classes of Boolean functions for which
$\mathsf{mbs}(f)=\mathsf{MCC}(f)$. We get that for such class of functions
$\mathsf{MCC}(f)=O(\log^{2}(\mathsf{spar}(f)))$ (an improvement over the
relationship $\mathsf{MCC}(f)=O(\log^{5}{\mathsf{spar}(f)})$ proved in [11]).

Theorem 1.3 states that if $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is monotone
or symmetric Boolean function, then

$\mathsf{ms}(f)=\mathsf{mbs}(f)=\mathsf{fmbs}(f)=\mathsf{MCC}(f).$

######  Proof (Proof of Theorem 1.3)

We prove the two cases separately.

Case 1 ($f$ is monotone): it suffices to show that for monotone Boolean
functions $\mathsf{MCC}(f)\leq\mathsf{ms}(f)$. Let $x$ be an input for which
$\mathsf{MCC}(f,x)=\mathsf{MCC}(f)$.

Without loss of generality assume that $f$ is monotonically increasing and
$f(x)=0$. Let $C$ be a minimal certificate for $f_{x}$ at the corresponding
all $0^{n-|x|}$ string s.t. $|C|=\mathsf{MCC}(f,x)$. Now consider the input
$y$ defined as follows:

$y_{i}:=\begin{cases}1&i\text{$\notin$ C}\\\ 0&i\text{$\in$ C}\end{cases}$

As $y$ agrees with the all zero string $0^{n-|x|}$ at the indices in $C$ we
have that $f_{x}(0)=f_{x}(y).$ Now we claim that each of the indices in $C$ is
sensitive for $f_{x}$ at $y$. If it wasn’t the case then there exists an $i\in
C$ s.t. $f_{x}(y^{\oplus i})=f_{x}(y)$. As $f_{x}$ is also monotone hence for
all $z\in\\{0,1\\}^{n-|x|}$ for which $\;y^{\oplus i}\geq z$ we have
$f_{x}(y^{\oplus i})\geq f_{x}(z)$.

For any string $z^{{}^{\prime}}\in\\{0,1\\}^{n-|x|}$ that agrees with
$0^{n-|x|}$ at the bits in $C\setminus{i}$ notice that $z^{{}^{\prime}}\leq
y^{\oplus i}$. Hence $0=f_{x}(y^{\oplus i})\geq f_{x}(z^{{}^{\prime}})=0$. But
this implies that $C\setminus\\{i\\}$ is a certificate for $f_{x}$ at
$0^{n-|x|}$ which is a contradiction.

Hence,

$\mathsf{MCC}(f)=\mathsf{MCC}(f,x)=\mathsf{ms}(f_{x},y)\leq\mathsf{ms}(f_{x})\leq\mathsf{ms}(f).$

Case 2 ($f$ is symmetric): again, it suffices to show that if
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is symmetric then

$\mathsf{MCC}(f)\leq\mathsf{ms}(f).$

Let $x\in\\{0,1\\}^{n}$ be one of the inputs for which
$\mathsf{MCC}(f)=\mathsf{MCC}(f,x)=C(f_{x},0^{n-|x|})$. Now, let $C$ be the
witness for $\mathsf{MCC}(f,x)$. If $|C|=n-|x|$ then this would imply that all
the bits of $0^{n-|x|}$ are sensitive for $f_{x}$. For the other case, i.e.
$|C|<n-|x|$,what we claim is that $\mathsf{MCC}(f,x)=\mathsf{MCC}(f,z)$ where
$z$ is the input
s.t.$\mathrm{supp}(z)=\mathrm{supp}(x)\cup\\{i:i\in[n]\setminus(\mathrm{supp}(x)\cup
C)\\}$ i.e. z is set to $1$ at the bits lying in $\mathrm{supp}(x)$ and all
the bits not lying in $C$.

We claim that $\mathsf{MCC}(f,z)=C(f_{z},0^{n-|z|})=|C|=n-|z|$ i.e. all the
bits of $0^{n-z}$ are sensitive for $f_{z}$. If we assume this is not the case
i.e. $C^{{}^{\prime}}\subsetneq C$ is a certificate for $0^{n-|z|}$ with
$|C^{{}^{\prime}}|=|C|-1$ then it would imply that $C^{{}^{\prime}}$ is also a
certificate for $0^{n-|x|}$.

To argue this, say $C^{{}^{\prime}}=C\setminus i$. Now for any input $x<y<z$
that agrees with $0^{n-|x|}$ at the bits of $C^{{}^{\prime}}$ we have that
$f_{x}(0^{n-|x|})=f_{x}(y)$. This is from using the fact that $f_{x}$ is
symmetric, hence we can always swap the $i-th$ bit of $y$ with a zero bit in
$y$ not lying in $C$.

Hence by the above argument we would have that $C^{{}^{\prime}}$ is a
certificate for $0^{n-|x|}$ as well. But this contradicts the condition that
$\mathsf{MCC}(f,x)=|C|$

Using Theorem 1.3, we get the following corollary.

###### Corollary 6

Consider a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$.

  1. 1.

If $f$ is monotone,
$\mathsf{MCC}(f)=\mathsf{fmbs}(f)=\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$.

  2. 2.

If $f$ is symmetric,
$\mathsf{MCC}(f)=\mathsf{fmbs}(f)=\mathsf{mbs}(f)=(1+o(1))\log(\mathsf{spar}(f))$.

###### Proof

For the statement about monotone functions, we combine Theorem 1.3 with the
relation $\mathsf{mbs}(f)=O(\log^{2}(\mathsf{spar}(f)))$ [11, 5].

For symmetric functions, we use the relations
$D^{cc}(f\circ\wedge_{2})\leq(1+o(1))\log(\mathsf{spar}(f))$ [5] and
$\mathsf{mbs}(f)\leq D^{cc}(f\circ\wedge_{2})$ [11].

Note that the bound above for symmetric functions is tight as can be seen by
considering the $\mathsf{OR}$ function which has sparsity $2^{n}-1$ and
monotone sensitivity $n$.

##  Appendix 0.E Examples of separations for monotone measures

| $\mathsf{ms}$ | $\mathsf{mbs}$ | $\mathsf{fmbs}$ | $\mathsf{HSC}$ | $\log(\mathsf{spar})$
---|---|---|---|---|---
$\mathsf{ms}$ |  | $1$ | $1$ | $1$ | $2$
$\mathsf{mbs}$ | ? |  | $1$ | $1$ | $2$
$\mathsf{fmbs}$ | ? | $2$ |  | $1$ | $4$
$\mathsf{HSC}$ | ? | ? | ? |  | $5$
Table 1: Known relations for monotone measures: Entry $b$ in row $A$ and
column $B$ represents, for any function $f$, $A(f)=O(B(f))^{b+o(1)}$,

Here, we note some observations about monotone measures that follow from
previous work. We have listed all the known relationships between complexity
measures in Table 1. All non-trivial relationships follow from the results of
Knop et. al. [11]. A similar table for standard measures was compiled in [3].
The relationships between standard measures do not seem to straightforwardly
imply relationships between monotone combinatorial measures. On the bright
side, almost all the existing separations between classical complexity
measures can be lifted for a monotone analogue of complexity measures,
essentially in the same way as the proof of Theorem 1.2 as we explain later.
For the relation part, it is natural and interesting to ask if monotone
measures are polynomially related at all. Note that a row with
$\log(\mathsf{spar})$ doesn’t make sense since it is not polynomially related
to other monotone complexity measures.

#### Why we don’t need a row for $\log(\mathsf{spar})$?

The function $(\and_{n}\circ\mathsf{OR}_{2})$ (example 2.18 in Knop et al
[11]) has sparsity exponential in $n$ but constant $\mathsf{MCC}$. So $\
log(\mathsf{spar})$ can not be bounded by any polynomial power of the monotone
complexity measures.

#### Lifting separations between classical measures for monotone measures:

Let $M_{1},M_{2}\in\\{\mathsf{s},\mathsf{bs},\mathsf{fbs},\mathsf{C}\\}$ and
let $mM_{1},mM_{2}$ denote their respective monotone analogues. Suppose $f$
achieves a separation $M_{1}(f)\geq\Omega(M_{2}(f)^{c})$ and suppose $y$ is
the input where $M_{1}(f)=M_{1}(f,y)$. Consider the shifted function $g$ which
maps $x$ to $f(xXORy)$. Then
$mM_{1}(g,0^{n})=M_{1}(f,y)=M_{1}(f)\geq\Omega(M_{2}(f)^{c})=\Omega(M_{2}(g)^{c})\geq\Omega(mM_{2}(g)^{c})$.

We will give a precise example of the fact that classical separations can be
lifted easily for monotone measures.

For example in terms of monotone measures [11] proved that
$\mathsf{fmbs}(f)=O(\mathsf{mbs}(f)^{2})$ for all Boolean function $f$. It is
natural to ask if the relation is tight or not. Consequently it comes to the
best known separations between $\mathsf{fbs}$ and $\mathsf{bs}$ and to check
if that example works for monotone measures as well. There exist classes of
functions given by [8] that gives separations between $\mathsf{fbs}$ and
$\mathsf{bs}$. Let us denote the function introduced by [8] by $\mathsf{GSS}$.

######  Theorem 0.E.1 ([8])

There exists a family of Boolean functions $\mathsf{GSS}$ for which
$\mathsf{fbs}(\mathsf{GSS})=\Omega(\mathsf{bs}(\mathsf{GSS})^{\frac{3}{2}})$.

Now $\mathsf{GSS}$ function is such that
$\mathsf{fbs}(\mathsf{GSS}(0^{n}))=\Omega(n^{\frac{3}{4}})$ and
$\mathsf{bs}(\mathsf{GSS})=O(n^{\frac{1}{2}})$. Now, from the definition of
monotone measures, it follows that
$\mathsf{fmbs}(\mathsf{GSS}(0^{n}))=\Omega(n^{\frac{3}{4}})$ and
$\mathsf{mbs}(\mathsf{GSS})=O(\mathsf{bs}(\mathsf{GSS}))=O(n^{\frac{1}{2}})$.
Consequently, we have the following lemma,

###### Lemma 6

There exists Boolean function for which,
$\mathsf{fmbs}(\mathsf{GSS})=\Omega(\mathsf{mbs}(\mathsf{GSS})^{\frac{3}{2}})$

Note that the above separation is not tight but it matches the best-known
separations for standard measures $\mathsf{fbs}$ and $\mathsf{bs}$.


# Atmospheric neutrino spectrum reconstruction with JUNO

, Stefano M. Mari, Cristina Martellini, Paolo Montini, on behalf of the JUNO
Collaboration
Università degli Studi Roma 3 & INFN, sezione di Roma 3
E-mail Corresponding author

###### Abstract:

The atmospheric neutrino flux represents a continuous source that can be
exploited to infer properties about Cosmic Rays and neutrino oscillation
physics. The JUNO observatory, a 20 kt liquid scintillator currently under
construction in China, will be able to detect atmospheric neutrinos , given
the large fiducial volume and the excellent energy resolution. The light
produced in neutrino interactions will be collected by a double-system of
photosensors: about 18.000 20” PMTs and about 25.000 3” PMTs. The rock
overburden above the experimental hall is around 700 m and the experiment is
expected to complete construction in 2021.
In this study, the JUNO performances in reconstructing the atmospheric
neutrino spectrum have been evaluated. The different time evolution of
scintillation light on the PMTs allows to discriminate the flavor of the
primary neutrinos. To reconstruct the time pattern of events, the signals from
3” PMTs only have been used, because of the small time resolution. A
probabilistic unfolding method has been used, in order to infer the primary
neutrino energy spectrum by looking at the detector output. The simulated
spectrum has been reconstructed between 100 MeV and 10 GeV, showing a great
potential of the detector in the atmospheric low energy region. The
uncertainties on the final flux, including both statistic and the systematic
contributions, range between 10% and 25%, with the best performances obtained
at the GeV.

##  1 Introduction

The origin and properties of Cosmic Rays (CRs) are still matter of study by a
number of experiments. A fraction of the energy of an air shower, resulting
after a CR interaction in the atmosphere, is carried by neutrinos. The
atmospheric $\nu$ flux is almost entirely composed of ${\nu_{\mu}}$ and
${\nu_{e}}$111Here, and in all the text, in $\nu_{\mu}$ and $\nu_{e}$ we
include also the corresponding antineutrinos. and spans many decades in
energy, from the MeV up to the PeV scale. Neutrinos travelling across the
Earth can be also used as a probe to study flavor oscillation effects in
matter. After the experimental results in past years [1, 2, 3, 4, 5, 6],
further contributions to the atmospheric $\nu$ spectrum will come from the
next generation of neutrino detectors, operating in the next decade. JUNO is a
large liquid scintillator (LS) detector with low energy threshold and low
energy resolution ($\sim 3\%/\sqrt{E~{}[MeV]}$), currently under construction
in China [7]. Its core consists of a $\sim$36 m diameter acrylic sphere, which
will be filled with 20 kt of liquid scintillator. The light produced in $\nu$
interactions will be collected by two independent systems of photosensors:
sabout 18.000 20” PMTs and 25.000 3” PMTs, respectively. Given the large
fiducial volume and the excellent energy resolution, JUNO will be able to
detect atmospheric neutrinos. The expected event rate is of the order of
several $\nu$ interactions/day. The central sphere is surrounded by a
cylindrical water pool, which acts as an active veto against cosmic muons. The
cherenkov light produced inside the pool will be observed by about 2.000 20”
PMTs. At the top of the system another detector, made of plastic scintillating
strips, will be assembled: the top tracker, whose role is to identify and
precisely track cosmic muons.

##  2 The Monte Carlo simulation

Since the JUNO detector is still under construction, the study relies on Monte
Carlo (MC) simulations only. The MC production has been processed in two main
steps:

  * •

Neutrino interactions generation within the detector volume. An initial flux
of atmospheric $\nu$ at the JUNO location has been assumed, according to the
predictions from [8]. The model provides also the zenith- and azimuth-angle
flux dependence and is calculated at the source. In order to get a realistic
flux at the detector, flavor oscillation effects have been applied to the
original flux, including both the vacuum and the matter contribution.
The interaction of neutrinos with the target materials has been managed by the
_GENIE Neutrino Monte Carlo Generator_ [9]. The interactions have been
generated with a neutrino energy distribution up to 20 GeV and consist of
$5\cdot 10^{5}~{}{\nu_{\mu}}+{\nu_{e}}$ events (fig. 1 \- left). The output of
the simulation is the full list of secondaries and their associated properties
(ID, momentum, direction $\dots$), including the type of interaction neutrinos
undergo, either a charged-current (CC) or a neutral-current (NC) one.

  * •

Propagation of secondaries in the scintillator by means of a _GEANT4-_ based
simulation [10], which includes energy losses, photon production and
propagation, photon-PMT cathode interaction and photo-electrons (PEs)
generation. Because of the JUNO very large active volume and the thousands of
PMTs, running a full simulation is both CPU and storage consuming, which puts
a limitation in the number of simulated events.

After the end of the simulation chain, a map of the hits on the detector is
available, distributed in time and position (fig. 1 \- right).

Figure 1: Left: visible energy of the MC sample, for $\nu_{\mu}$ CC (blue),
$\nu_{e}$ CC (red) and NC events (green); right: map of the hits on the 3” PMT
system after one neutrino event ($E_{\nu}\simeq$ 900 MeV, $\nu_{e}$ CC
interaction).

##  3 Sample selection and flavor identification

Simulated atmospheric neutrino events are selected in order to get two
separate samples, one enriched in $\nu_{e}$ and the other one in $\nu_{\mu}$.
Being a large LS, the JUNO central detector is not the ideal instrument for
particle tracking. Indeed, its best performances are achieved in events which
are entirely contained within the volume, where a full calorimetric
measurement can be performed, with no need to separate the single tracks.
Fiducial cuts applied to the neutrino sample are targeted to select events
whose secondaries start and end within the CD, here called fully-contained
(FC). On the contrary, events which have some secondary particles escaping
from the CD are defined partially-contained (PC) and will have poorer energy
resolution. Muons that may come from neutrino interactions outside the
detector are not considered in the study. On the other hand, the above
criteria form an intrinsic limitation for the spectrum reconstruction of high-
energy $\nu_{\mu}$, namely $E_{\nu_{\mu}}\gtrsim$10 GeV, because the resulting
muon from a CC interaction is never fully contained inside the CD.
In order to select FC well-reconstructed events and enrich the sample in CC
interactions, a series of fiducial cuts have been applied:

$\mathbf{R_{VERTEX}<16\,m}.$

The cut on the vertex distance from the centre of the sphere $R_{VERTEX}$ has
been used to remove events which release their energy near the edge of the
acrylic sphere. These events tipically exhibit a loss of linearity between the
deposited and the collected energy, because part of the energy is released in
the acrylic and not in the LS and because the closest PMTs collect a great
amount of light and can undergo saturation. In order to reproduce the
uncertainty on the reconstructed vertex position, the true MC position has
been smeared by means of a 3D gaussian function, centered at the true position
and with the square root of the variance $\sigma$ = 1 m.

$\mathbf{NPE_{LPMT}^{CD}>10^{5}}.$

To remove the core of NC events, which accumulates at low energy (fig. 1 \-
left), a cut on the total charge collected by the 20” PMT system in the inner
detector has been employed (NPE $\equiv$ Number of Photo-Electrons). $10^{5}$
PEs roughly correspond to a visible energy of 80 MeV.

$\mathbf{NPE^{WP}<60}.$

The cut on the total charge collected in the water pool has been used to
remove cosmic muon events and PC neutrino events.

The overall efficiency of fiducial cuts on the neutrino sample is about 60%.
After the selection, the neutrino sample is composed at 97% of FC events. The
remaining PC events are composed at 96% of $\nu_{\mu}$ CC interactions. To
estimate the residual contamination coming from atmospheric muons, a full MC
simulation of millions of events would be necessary, since the muon flux is
several orders of magnitude higher than the atmospheric neutrino flux.
However, since these kind of simulations are extremely CPU-consuming, a
simplified 2D toy model has been implemented. The model simulates all the
physical processes for light production and detection, including the
stochastic fluctuations. As a validation, the model is able to reproduce the
expected performances of the water pool veto (98% efficiency) if a simple
majority is requested to tag cosmic muon events. The estimated rejection power
is $<1.15\cdot 10^{-6}$ @ 90% confidence level, after the fiducial cuts.
A crucial part in the atmospheric $\nu$ study is the correct identification of
the original $\nu$ flavor. Above $\sim$100 MeV neutrinos can be assumed to
interact with nucleons only. This implies that hadronic particles are always
produced in the final state. In the case of a CC interaction, the
corresponding charged lepton is also produced (either
$\nu_{\mu}~{}N\rightarrow\mu~{}X$ or $\nu_{e}~{}N\rightarrow e~{}X$). In the
case of a NC interaction, only secondary hadrons and the scattered neutrino
are in the final state. CC interactions are therefore the preferred channel
for the neutrino flavor identification, since the lepton immediately
identifies the original neutrino. Specifically, muons with energy ¿ 1 GeV
travel in general for a longer distance inside the detector with respect to
electrons. Additionally, muons can decay inside the scintillator volume,
giving a delayed energy release at low energy too. The above differences make
$\nu_{\mu}$ CC events more elongated in time with respect of $\nu_{e}$ CC
events, which indeed appear more point-like. Hadronic particles, which make
the totality of a NC event, have in general a long-living energy release,
because of interactions and decays. Furthermore, since hadrons are included in
every neutrino-nucleon interaction, they make more similar $\nu_{\mu}$ and
$\nu_{e}$ CC event topologies.
The different temporal behaviour of the classes of events has been exploited
by building a time profile-based discrimination algorithm. The 3” PMT system
only has been used in the algorithm, since it is more accurate in time
measurement. To reproduce realistic Time-Transit Spread (TTS) effects, an
artificial smearing has been applied to the true hit time over every PMT. A
gaussian function with $\sigma=4~{}ns$ has been used. A hit time-residual is
then defined for each SPMT as:

$t_{res}^{i}=t_{hit}^{i}-\left(\frac{n\cdot R_{V}^{i}}{c}\right),$ (1)

where $t_{hit}^{i}$ is the hit time on the i-th SPMT, $c/n$ is the speed of
light inside the scintillator and $R_{V}^{i}$ is the distance between the i-th
SPMT and the interaction vertex. The smeared vertex position is again used.
The time residual is therefore the arrival time of light on the PMTs, minus
the time of flight of photons from the vertex to the PMT and reflects how
smeared in time is the event.
Since $\nu_{\mu}$ and $\nu_{e}$ CC events result in different light production
duration, the RMS of the $t_{res}$ distribution is used as a discrimination
variable (here called $\sigma(t_{res})$). In fig. 2 the $\sigma(t_{res})$
distribution is reported for the three populations: $\nu_{\mu}$ CC, $\nu_{e}$
CC and NC events. The variable is also reported separately in 4 different bins
of NPE collected by CD LPMTs, selected in order to have equal statistics in
each bin.

Figure 2: Distribution of $\sigma(t_{res})$ for $\nu_{\mu}$ CC (blue),
$\nu_{e}$ CC (red) and NC events (green). The NPE range is reported above the
figures.

A good isolation of the $\nu_{e}$ CC component is evident, over the whole
energy range. On the contrary, the $\nu_{\mu}$ CC and the NC components appear
to be overlapped. The hadronic part of the secondaries has indeed an important
contribution from charged pions, which decays with $\sim$100% probability into
$\mu+\nu$ and are therefore an irreducible background. Also protons and
neutrons have timing features similar to muons, because they scatter for a
long time before stopping. The NC component contribution, however, becomes
less significant at high energy, because of the steeper spectral shape (fig. 1
\- left). Two separate cuts have been therefore applied for $\nu_{e}$ and
$\nu_{\mu}$, to isolate CC events. The residual NC events, which have not been
removed by the $t_{res}$ selection, are populated both of $\nu_{e}$ and
$\nu_{\mu}$.
Concerning the $\nu_{e}$ selection, a value of $\sigma(t_{res})<$ 75 ns is
required. The cut results in an efficiency about 41% with respect to the
sample after fiducial cuts and a residual contamination from $\nu_{\mu}$ less
than 6%. For the $\nu_{\mu}$ selection, a requirement of $\sigma(t_{res})>$ 95
ns is coupled to a further requirement of NPE ¿ 500.000. The efficiency is 60%
with respect to the sample after fiducial cuts. The residual $\nu_{e}$
contamination is less than 20%.

##  4 Spectrum reconstruction

In order to extract the primary neutrino energy spectrum, an unfolding
procedure has been used. The observable spectrum $M_{j}$, which in this case
is the NPE${}^{CD}_{LPMT}$ distribution, is the result of:

$M_{j}=\sum_{i}A_{ji}N_{i},$ (2)

where $N_{i}$ is the unfolded neutrino spectrum and $A_{ji}$ is the detector
response matrix, which can also be expressed as the conditional probability
that a neutrino with a certain energy produces a certain amount of NPE:
$A_{ji}=P\left(NPE^{CD}_{LPMT_{j}}|E_{v_{i}}\right)$. The relationship can be
inverted and the primary spectrum can be expressed as:

$N_{i}=\sum_{j}\boldsymbol{U}_{ij}\boldsymbol{M}_{j},$ (3)

where $U_{ij}$ is the unfolding matrix. To build $U$, an iterative Bayesian
method has been adopted [11, 12]. The detector response matrix has been
estimated using the full MC sample and then normalized as
$\sum_{j}A_{ji}=1-\epsilon$, where $\epsilon$ takes into account the
inefficiency due to the reduced phase space considered by the matrix. As a
prior flux distribution, the prediction from [8] has been used. The two
unfolding matrices, for the $\nu_{e}$ and the $\nu_{\mu}$ flux, are reported
in fig. 3. As for the $A$ matrix, the unfolding matrix can be expressed as the
conditional probability that an event which produced a certain amount of NPE
originated from a neutrino with a certain energy:
$U_{ij}=P\left(E_{\nu_{i}}|NPE^{CD}_{LPMT_{j}}\right)$: $U$ allows therefore
to unfold the experimentally observed NPE distribution into the primary
neutrino flux.

Figure 3: Unfolding matrices for the $\nu_{e}$ (left) and the $\nu_{\mu}$ flux
(right).

An independent MC sample, corresponding to about 5 years of detector livetime,
have then be generated, to simulate real data. The primary neutrino spectrum
has been reconstructed separately for $\nu_{e}$ and $\nu_{\mu}$ and is
reported in fig. 4, together with the prediction from [8] and the measurement
presented in [4].

Figure 4: Reconstructed atmospheric neutrino spectrum for $\nu_{e}$ (left) and
$\nu_{\mu}$ (right). The prediction from [8] is also shown, w/ (full line) and
w/o (dashed line) the oscillation effects. The measurement from [4] is
reported (white crosses).

The uncertainties reported in the spectra in fig. 4 include both the statistic
and the systematic contribution. In the second class, the effects from
oscillations parameters and cross sections uncertainty, sample selection and
probability matrices building have been included. The total uncertainty ranges
between 10% and 25%, with the best performances obtained around the GeV.

##  5 Conclusions

The JUNO experiment, once completed, will be the largest liquid scintillator-
based detector ever built. Among the many physics goals that JUNO is able to
achieve, the atmospheric neutrino sector represents a target that can be
addressed in the first years of data-taking. The large detector volume and the
fine energy resolution allow the measurement of the atmospheric neutrino flux
in the energy range [100 MeV - 10 GeV], with an uncertainty ¡ 25%. An event
time-profile algorithm has been used for the $\nu_{e}$/$\nu_{\mu}$ separation.
The flux measurement will provide information from an interesting energy
region, where the oscillation effects are maximal and theoretical models have
significative uncertainties.

## References

  * [1] K. Daum et al. (Fréjus Collaboration), Z. Phys. C 66, 417 (1995).
  * [2] R. Abbasi et al., Astrop. Phys. 34, 48-58, (2010).
  * [3] S. Adrián-Martínez et al., Eur. Phys. J. C 73, 2606 (2013).
  * [4] E. Richard et al. (Super-Kamiokande Collaboration), Phys. Rev. D 94, 052001 (2016).
  * [5] M. G. Aartsen et al. (IceCube Collaboration), Phys. Rev. D 91, 122004 (2015).
  * [6] M. G. Aartsen et al. (IceCube Collaboration), Eur. Phys. J. C 77, 692 (2017).
  * [7] F. An et al., Journ. of Phys. G: Nucl. and Part. Phys. 43, 030401 (2016).
  * [8] M. Honda, M. Sajjad Athar, T. Kajita, K. Kasahara, and S. Midorikawa, Phys. Rev. D 92, 023004 (2015).
  * [9] C.Andreopoulos et al., Nucl. Instrum. Meth. A614 87-104 (2014).
  * [10] F. An et al., J. Phys.: Conf. Ser. 664 072053 (2015).
  * [11] G. D’Agostini, Nucl. Instrum. Meth. Phys. Res., Sect. A 362, 487 (1995).
  * [12] G. D’Agostini, arXiv:1010.0632 (2010).