# On the Sensitivity Conjecture for Disjunctive Normal Forms

Karthik C S †1, Sébastien Tavenas

► To cite this version:

Karthik C S †1, Sébastien Tavenas. On the Sensitivity Conjecture for Disjunctive Normal Forms. 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Dec 2016, Chennai, India. 10.4230/LIPIcs.FSTTCS.2016.15 . hal-02447444

HAL Id: hal-02447444

https://hal.science/hal-02447444

Submitted on 21 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Sensitivity Conjecture for Disjunctive Normal Forms*

Karthik C. S.†¹ and Sébastien Tavenas‡²

1 Weizmann Institute of Science, Israel
karthik.srikanta@weizmann.ac.il

2 Microsoft Research, India
t-sebat@microsoft.com

## Abstract

The sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function $f$, the maximum sensitivity $s(f)$, is polynomially related to its block sensitivity $bs(f)$, and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open.

In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function $f$ admitting the Normalized Block property, $bs(f) \le 4s(f)^2$. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property.

Recently, Gopalan et al. [ITCS'16] showed that every Boolean function $f$ is uniquely specified by its values on a Hamming ball of radius at most $2s(f)$. We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.

**1998 ACM Subject Classification** F.1.1 Models of Computation

**Keywords and phrases** Boolean function, Sensitivity, Block sensitivity, DNF

**Digital Object Identifier** 10.4230/LIPIcs.FSTTCS.2016.15

## 1 Introduction

Sensitivity and block sensitivity are complexity measures that are commonly used for Boolean functions. Both these measures were originally introduced for studying the time complexity of CRAW-PRAM's [7, 8, 15]. Block sensitivity is polynomially related to a number of other complexity measures, such as the decision-tree complexity, the certificate complexity, the polynomial degree, and the quantum query complexity [5]. A longstanding open problem is the relation between sensitivity and block sensitivity. From the definitions of sensitivity and block sensitivity, it immediately follows that $s(f) \le bs(f)$, where $s(f)$ and $bs(f)$ denote the sensitivity and the block sensitivity of a Boolean function $f$. Nisan and Szegedy [16] conjectured that sensitivity is also polynomially related to block sensitivity:

► **Conjecture 1 (Sensitivity Conjecture [16]).** *There exist constants $\delta, c > 0$ such that for every Boolean function $f$ we have that $bs(f) \le c \cdot (s(f))^\delta$.*

<figure><img src="image_2.png" /></figure>

<footnote>* A full version of the paper is available at https://arxiv.org/abs/1607.05189.</footnote>

<footnote>† This work was partially supported by Irit Dinur's ERC-StG grant number 239985. Some parts of this work were done while interning at Microsoft Research, India.</footnote>

<footnote>‡ This work was supported by ANR project CompA (project number: ANR-13-BS02-0001-01).</footnote>
15:2 On the Sensitivity Conjecture for Disjunctive Normal Forms

This conjecture is still widely open and the best known upper bound on block sensitivity is exponential in terms of sensitivity [1]. On the other hand, the best known separation (through an example of a Boolean function) between sensitivity and block sensitivity is quadratic [3]; more background and discussion about the sensitivity conjecture can be found in the survey of Hatami et al. [12].

Over the last decade, in the majority of the works concerning the sensitivity conjecture, the focus has been on addressing the conjecture for restricted classes of Boolean functions, where the restriction is imposed by some notion of symmetry [6, 18, 9]. The reason behind pursuing this direction is that nonconstant Boolean functions with a high degree of symmetry must have high complexity according to various measures. Accordingly, all the results in this direction [6, 18, 9] show that the sensitivity of the corresponding functions is large (in terms of the number of variables), and deduce that the sensitivity is close to block sensitivity. While we feel that proving the sensitivity conjecture for a restricted class of Boolean functions is a step in the right direction, we would like to argue that these specific restrictions are limited in their potential to explicitly promote the understanding of the relationship between sensitivity and block sensitivity.

In this paper, we prove the sensitivity conjecture for a restricted class of Boolean functions, where the restriction is imposed on a DNF representation of the function. This is one of the first time[s] since Nisan [15] that the sensitivity conjecture is proved for a restriction based on a model of computation (recently, Lin and Zhang [14] proved the sensitivity conjecture for functions admitting circuits with a small number of negation gates, and in a simultaneous work [4], the authors prove the sensitivity conjecture in the case of regular read-k formulas of constant depth with k constant). Informally, the restriction we impose on the DNF can be described as follows. We assume that the maximal block sensitivity is reached on the all zeroes input and that the function outputs a zero on this input, and notice that for each clause in the DNF, the set of positive literals in the clause corresponds to a sensitive block. Based on the fact that the block sensitivity counts the number of disjoint sensitive blocks, we consider the natural restriction where the set of positive literals of each of the clauses are also disjoint. We say that any function adhering to this restriction admits the normalized block property, and we show that for any Boolean function f admitting the normalized block property, $bs(f) < 4s(f)^2$.

As the other side of the same coin, this result provides a barrier to building Boolean functions with super-quadratic separation between sensitivity and block sensitivity. Currently, the best known separation is given by an example of Ambainis and Sun [3] who built a function f with $bs(f) = \frac{2}{3}s(f)^2 - \frac{1}{3}s(f)$. Ambainis and Sun additionally showed that their example gives the best possible separation (up to an additive factor) between sensitivity and block sensitivity for all functions that are an OR of functions whose zero-sensitivity equals 1. We build a framework (of restrictions) over DNFs and identify where the result of Ambainis and Sun lies within this framework, and our result that the sensitivity conjecture is true for Boolean functions admitting normalized block property is shown to be an extension of the result of Ambainis and Sun. Additionally, Kenyon-Kutin [13], showed that if the block sensitivity is attained on some input which has blocks of size at most two then, $bs \le e \cdot s^2$. More generally,

**Theorem 2 (Kenyon and Kutin [13]).** For every Boolean function f on n variables, and every $\ell \in \{2, \dots, s(f)\}$, we have:

$$bs_{\ell}(f) \le \frac{e}{(\ell-1)!} (s(f))^{\ell},$$

where $bs_{\ell}(f)$ is the block sensitivity of f when each block is restricted to be of size at most $\ell$.
Therefore, to construct examples of Boolean function with super-quadratic separation between sensitivity and block sensitivity we now have two barriers. Moreover, we extend the notion of block property to *t*-block property, and prove a lower bound on the sensitivity of Boolean functions admitting the *t*-block property in terms of *t*, and the width and size of the DNF.

Recently, Gopalan et al. [11] investigated the computational complexity of low sensitivity functions and provided interesting upper bounds on their circuit complexity. This was indicated to be a promising alternative approach to the sensitivity conjecture as opposed to getting improved bounds on specific low level measures like block sensitivity or decision tree depth [13, 1, 3]. In particular, they showed that every Boolean function *f* is uniquely specified by its values on a Hamming ball of radius at most 2s(*f*), and showed various applications of this result. We extend this result by showing that if two Boolean functions *f* and *g* coincide on a ball of radius s(*f*) + s(*g*) then, *f* = *g*. Furthermore, for every *p*, *q* > 1, we construct examples of Boolean functions *f* and *g* such that s(*f*) = *p*, s(*g*) = *q*, and *f* and *g* coincide on a ball of radius s(*f*) + s(*g*) - 1 but *f* ≠ *g*, showing that the above result is tight.

Finally, we propose a computational problem motivated by the sensitivity conjecture,
and the existing work and results therein. Assuming the sensitivity conjecture to be true, we
note that this problem is in **TFNP**, and wonder if resolving the sensitivity conjecture would
yield an efficient algorithm to this computational problem.

This paper is organized as follows. In Section 2, we provide the basic definitions of complexity measures, structures, and objects that will be used in the rest of the paper. In Section 3, we define a few restrictions (such as the block property) on DNFs representing Boolean functions and prove the sensitivity conjecture for the class of functions admitting (some of) these structural restrictions. In Section 4, we investigate a structural result of low sensitivity functions. In Section 5, we propose a new computational problem motivated by the sensitivity conjecture. Finally, in Section 6, we conclude with a promising open question on proving the sensitivity conjecture for functions admitting the *t*-block property.

The missing proofs can be found in the full version of the paper.

2 Preliminaries

We use the notation $[n] = \{1, \dots, n\}$. Let $f : \{0, 1\}^n \to \{0, 1\}$, be a Boolean function. Let $x \in \{0, 1\}^n$. For $i \in [n]$, we denote by $x^i$ the input in $\{0, 1\}^n$ which is obtained by flipping the $i^{th}$ bit of $x$. Also for any $B \subseteq [n]$, we denote by $x^B$ the input in $\{0, 1\}^n$ which is obtained by flipping the bits of $x$ in all coordinates in $B$. We will now define two complexity measures on Boolean functions which are of great interest.

► **Definition 3.** The sensitivity of a Boolean function *f* at input *x* ∈ {0, 1}ⁿ, written *s*(*f*, *x*), is the number of coordinates *i* ∈ [*n*] such that *f*(*x*) ≠ *f*(*x*ᵢ). The sensitivity of *f*, written *s*(*f*), is defined as *s*(*f*) = maxᵢ∈{0,1}ⁿ *s*(*f*, *x*). We define *s*₁(*f*) = maxᵢ∈{0,1}ⁿ *s*(*f*, *x*) and *s*₀(*f*) = maxᵢ∈{0,1}ⁿ *s*(*f*, *x*).

**Definition 4.** The block sensitivity of a Boolean function *f* at input *x* ∈ {0, 1}ⁿ, for *k* disjoint subsets *B*₁, ..., *B*ₖ of [*n*] (called blocks), written **bs**(*f*, *x*, *B*₁, ..., *B*ₖ), is the number of blocks *i* ∈ [*k*] such that *f*(*x*) ≠ *f*(*x*<sup>*B*<sub>i</sub></sup>). The block sensitivity of a Boolean function *f* at input *x* ∈ {0, 1}ⁿ, written as **bs**(*f*, *x*), is the maximum of **bs**(*f*, *x*, *B*₁, ..., *B*ₖ) over all *k* disjoint subsets *B*₁, ..., *B*ₖ of [*n*] for all *k* ∈ [*n*]. The block sensitivity of *f*, written **bs**(*f*), is defined as **bs**(*f*) = max<sub>*x*∈{0,1}<sup>*n*</sup></sub> **bs**(*f*, *x*). We define **bs**₁(*f*) = max<sub>*f*(*x*)=1</sub> **bs**(*f*, *x*) and **bs**₀(*f*) = max<sub>*f*(*x*)=0</sub> **bs**(*f*, *x*).
15:4 On the Sensitivity Conjecture for Disjunctive Normal Forms

We will now introduce a model of representation of Boolean functions.

**Definition 5.** A DNF (disjunctive normal form) formula $\Phi$ over Boolean variables $x_1, \dots, x_n$ is defined to be a logical OR of terms, each of which is a logical AND of literals. A literal is either a variable $x_i$ or its logical negation $\bar{x}_i$. We insist that we can assume that no term contains both a variable and its negation (otherwise we can remove this term). We often identify a DNF formula $\Phi_f$ with the Boolean function $f: \{0, 1\}^n \to \{0, 1\}$ it computes.

We note here that for every Boolean function $f$, there exists at least one (it is not unique) DNF formula $\Phi_f$ that computes it.

3 Block Property

In the following, we will often use the notation $\lor$ (respectively $\land$) for denoting the Boolean operation OR (respectively AND). Let $f$ be a Boolean function and $\Phi_f$ be one of its DNF formulas. Let $X = \{x_1, \dots, x_n\}$ be the set of variables. Let $d_\lor$ be the fan-in of the $\lor$-gate which is usually called the size of the DNF. We label the $d_\lor$ $\land$-gates as: $\land_1, \dots, \land_{d_\lor}$. Let $d_{\land_i}$ be the fan-in of $\land_i$. Let $d_\land = \max_i d_{\land_i}$ be the width of the DNF. For every $i \in [d_\lor]$, let $A_i$ be the set of variables amongst the literals connected to $\land_i$ appearing **without** a negation and let $\bar{A}_i$ be the set of variables amongst the literals connected to $\land_i$ appearing **with** a negation. An assignment of the variables is a function $\sigma: X \to \{0, 1\}$. For every $\land_i$, we define $S_i$ as follows:

$$S_i = \{\sigma | \land_i(\sigma) = 1\},$$

where $\land_i(\sigma)$ is the evaluation of $\land_i$ when the assignment to the variables is given by $\sigma$.

By negating some variables and/or negating the output of the function, we can always assume that the maximum block sensitivity is the maximum 0-block sensitivity (i.e., $\mathbf{bs}_0$) and is reached on the all zeros input. Moreover, given a DNF representation of our function, we can assume that this representation is minimal (i.e., any subformula of the given formula computes a distinct function).

**Definition 6.** A Boolean function $f$ represented by a DNF formula $\Phi_f$ is said to be represented in **compact form** if the following holds:

(a) $f(0^n) = 0$,

(b) The maximum 0-block sensitivity is attained on the all zeroes input, i.e., $\mathbf{bs}_0(f) = \mathbf{bs}(f, 0)$,

(c) and $\forall i \in [d_\lor]$, we have that $S_i \setminus \bigcup_{j \neq i} S_j \neq \emptyset$.

Moreover the representation is called **normalized** if the maximal block sensitivity is also attained on the all zeroes input, i.e., $\mathbf{bs}(f) = \mathbf{bs}(f, 0)$.

The condition (c) means that for each $i$ there exist a $\sigma$ such that $\sigma$ makes only $\land_i$ true.

**Lemma 7.** For every $f: \{0, 1\}^n \to \{0, 1\}$, there exists $f' : \{0, 1\}^n \to \{0, 1\}$ such that $\mathbf{s}(f') = \mathbf{s}(f)$, $\mathbf{bs}(f') = \mathbf{bs}(f) = \mathbf{bs}(f', 0^n)$, and $f'$ admits a normalized compact form representation.

**Proof.** We claim that for any Boolean function $f$, there exists another Boolean function $f'$ such that $\mathbf{s}(f) = \mathbf{s}(f')$, $\mathbf{bs}(f) = \mathbf{bs}(f')$, $f'(0^n) = 0$ and such that $f'$ attains its maximal block sensitivity at the all zeroes input. This is because, if $f$ attains its maximum block sensitivity at $a \in \{0, 1\}^n$ then, we define $f'(x) = f(a) \oplus f(x \oplus a)^1$, and the claim follows.

<footnote n="1">¹ The operator $\oplus$ denotes the usual XOR function.</footnote>
Let us fix a DNF formula for $f'$. If there is $i \in [d_\vee]$ such that $S_i \subseteq \bigcup_{j \neq i} S_j$, then we do not change the function by removing $\wedge_i$. Thus any such AND gates can be assumed to have been removed. ◀

In fact, we can remark that only the condition $f(0^n) = 0$ from Definition 6 may need a larger DNF (since, it could need to compute the negation of the original function), other constraints can be achieved without increasing the size of the formula.

We will now describe a structural result about Boolean functions that admit compact form representation. For every $i \in [d_\vee]$, we define $\Gamma_i$ as follows:

$$ \Gamma_i = \{j \mid |A_i \cap \bar{A}_j| + |A_j \cap \bar{A}_i| = 1\}. $$

Informally, $\Gamma_i$ is the set of AND gates which contradict on $\wedge_i$ on exactly one variable. Let $\Gamma = \max_i |\Gamma_i|$. We bound $\mathbf{s}_1$ using $\Gamma$ as follows:

**Lemma 8.** Any Boolean function $f$ represented in the compact form admits the following bound on $\mathbf{s}_1$: $d_\wedge - \Gamma \le \mathbf{s}_1 \le d_\vee$.

**Proof.** First, we prove that $\mathbf{s}_1 \le d_\wedge$. Let $a \in \{0, 1\}^n$ be the input for which the maximum $\mathbf{s}_1$ is attained. By definition of $\mathbf{s}_1$, we have that $f(a) = 1$. Let $\wedge_i$ be an AND gate such that $\wedge_i(a) = 1$. Suppose $\mathbf{s}_1 > d_\wedge$ then there exists $x_j \in X \setminus (A_i \cup \bar{A}_i)$ such that $f(a^j) = 0$. But, as $\wedge_i$ does not depend on $x_j$, $\wedge_i(a^j) = 1$ and so $f(a^j)$ still equals 1, which is a contradiction.

We will now prove that $\mathbf{s}_1 \ge d_\wedge - \Gamma$. Let $i_0 = \underset{\wedge_i}{\operatorname{argmax}} d_{\wedge_i}$. Let $b \in S_{i_0} \setminus \bigcup_{j \neq i_0} S_j$ (from Definition 6c such a selection is possible). We have that $\wedge_{i_0}(b) = 1$ and for all $j \in [d_\vee] \setminus \{i_0\}$, $\wedge_j(b) = 0$. It is sufficient to lower bound the cardinality of $C \subseteq [n]$ such that for all $i \in C$, we have that $f(b^i) = 0$. Fix some $x_k \in (A_{i_0} \cup \bar{A}_{i_0})$. We observe that $f(b^k) = 1$ implies that there is an AND gate $\wedge_j$ such that $(A_{i_0} \cap \bar{A}_j) \cup (\bar{A}_{i_0} \cap A_j) = \{x_k\}$. There are exactly $|\Gamma_{i_0}|$ such $k$'s. The lower bound follows. ◀

Nisan [15] showed that for all monotone functions the block sensitivity and sensitivity are equal. This was the first time that the sensitivity conjecture was proven for a class of functions captured by a restriction on the model of computation for Boolean functions. In our setting, Nisan's result would be written as follows:

**Theorem 9 (Nisan [15]).** Let $f$ be a Boolean function and $\Phi_f$ be a compact form representation of $f$. In $\Phi_f$ if for every $i \in d_\vee$, we had that $\bar{A}_i = \emptyset$ then, $\mathbf{bs}(f) = \mathbf{s}(f)$.

In this paper, we look at Boolean functions through weaker restrictions on their DNF representation. In this regard, we will now see three kinds of structural impositions on Boolean functions in compact form representation. Later, we will prove the sensitivity conjecture for the class of functions admitting (some of) these structural impositions.

**Property 10 (Block property).** A Boolean function is said to admit the block property if under a compact form representation $\forall i, j \in [d_\vee]$ such that $i \neq j$, we have that $A_i \cap A_j = \emptyset$. Moreover, if there exists such a compact form representation which is also normalized, we will say that the function admits the normalized block property.

**Property 11 (Mixing property).** A Boolean function is said to admit the $\ell$-mixing property if under a compact form representation $\forall i, j \in [d_\vee]$ with $i \neq j$, such that if $(A_i \cup \bar{A}_i) \cap (A_j \cup \bar{A}_j) \neq \emptyset$ we have, $|(A_i \cap \bar{A}_j) \cup (A_j \cap \bar{A}_i)| \ge \ell$.

**Property 12 (Transitive property).** A Boolean function is said to admit the transitive property if under a compact form representation $\forall i, j, k \in [d_\vee]$, we have that if $(A_i \cup \bar{A}_i) \cap (A_j \cup \bar{A}_j) \neq \emptyset$ and if $(A_j \cup \bar{A}_j) \cap (A_k \cup \bar{A}_k) \neq \emptyset$ then, $(A_i \cup \bar{A}_i) \cap (A_k \cup \bar{A}_k) \neq \emptyset$.
15:6 On the Sensitivity Conjecture for Disjunctive Normal Forms

First, we see that if a Boolean function admits the Mixing property then we can improve
the bound obtained in Lemma 8.

► Lemma 13. Let $\ell > 1$. Any Boolean function admitting the $\ell$-mixing property has $\Gamma = 0$.

**Proof.** Fix $i \in [d_\vee]$. Since the function admits $\ell$-mixing property, we know that for every $j \in [d_\vee]$, either $(A_i \cup \bar{A}_i) \cap (A_j \cup \bar{A}_j) = \emptyset$ in which case we have that $j \notin \Gamma_i$, or $|(A_i \cap \bar{A}_j) \cup (A_j \cap \bar{A}_i)| \ge \ell$ in which case we again conclude that $j \notin \Gamma_i$ because of the following:

$$
1 < \ell \le |(A_i \cap \bar{A}_j) \cup (A_j \cap \bar{A}_i)| = |A_i \cap \bar{A}_j| + |A_j \cap \bar{A}_i|,
$$

where the last equality holds because in the definition of DNF formula we insisted that no
term contains both a variable and its negation. Therefore, we have that $\Gamma_i = \emptyset$. ◀

Consequently, we have that $\mathfrak{s}_1 = d_\wedge$, for all Boolean functions admitting the $\ell$-mixing property with $\ell > 1$.

Ambainis and Sun had previously shown in Theorem 2 of [3] that their construction gave
the (almost) best possible separation between block sensitivity and sensitivity for a family
of Boolean functions. Let us consider the Boolean functions $f$ which can be written as a
variables-disjoint union:

$$
f = \bigvee_{i=1}^{n} g(x_{i,1}, \dots, x_{i,m}). \tag{1}
$$

Then (see for example Lemma 1 in [3] or Proposition 31 in [10]) $\mathfrak{s}_1(f) = \mathfrak{s}_1(g)$, $\mathfrak{s}_0(f) = n\mathfrak{s}_0(g)$,
and $\mathfrak{bs}_0(f) = n\mathfrak{bs}_0(g)$. So if we can find a lower bound for the sensitivity of $g$ with respect
to $\mathfrak{bs}_0(g)$, we get the best gap for $f$ by choosing $n = \mathfrak{s}_1(g)/\mathfrak{s}_0(g)$.

► **Theorem 14** (Ambainis and Sun [3]). If $g$ is a Boolean function such that $s_0(g) = 1$ and $bs(g) = bs_0(g)$, then $2s_1(g) \ge 3 bs(g) - 1$.

In fact, we can notice that these functions belong to our framework (this claim is implicit
in their proof of Theorem 14, but we give a proof in the full version:

**► Claim 15.** Let $g$ be as in Theorem 14. Let $f$ be the OR of several copies of $g$, where each copy takes its input from a different set of variables, as in Eq. (1). Then, there exists $f'$ with same block sensitivity and at most same 1-sensitivity which admits the normalized block property, the transitive property, and the 3-mixing property.

Ambainis and Sun [3] present an explicit Boolean function $f$ such that $bs = \frac{2}{3}s^2 - \frac{1}{3}s$.
The function is a variables-disjoint union

$$
f = \bigvee_{i=1}^{3n+2} g(x_{i,1}, \dots, x_{i,4n+2}).
$$

The function $g$ outputs one if the $4n + 2$ corresponding variables satisfy the pattern $P_{\text{AmbainisSun}}$ or if it is the case after an even-length cyclic rotation of the variables. The pattern starts with $2n$ 0s which are followed by a block of two ones and it finishes by $n$ copies of the block $\underline{0}$ (the underscore means the variable can be 0 or 1):

<table>
  <tr>
    <td>0</td>
    <td>0</td>
    <td>...</td>
    <td>...</td>
    <td>0</td>
    <td>1</td>
    <td>1</td>
    <td>0</td>
    <td>&mdash;</td>
    <td>0</td>
    <td>&mdash;</td>
    <td>...</td>
    <td>...</td>
    <td>0</td>
    <td>&mdash;</td>
  </tr>
</table>
As we only admit the even-length rotations, we can easily see that the normalized block
property is ensured. The patterns in $g$ pairwise intersect, so we also get the transitive
property. Finally, if we consider two rotations $R_1$ and $R_2$ of the pattern, we can assume that
the **11-block** in $R_1$ intersects a **0**-block in $R_2$ (otherwise, we switch $R_1$ and $R_2$ and get it).
Then the **11-block** in $R_2$ will intersect a **00-block** in $R_1$. The two rotations of the pattern
disagree on at least three variables (and in fact exactly three). Hence the 3-mixing property
is also verified.

We show in the full version that other functions in literature achieving a quadratic gap (e.g. Rubinstein [17], Virza [19], Chakraborthy [6]) fall in our framework.

We ended up proving a result which supersedes the one mentioned in Theorem 14 both in the lower bound and for a more general family. The above lower bound is **exactly** matched by the Boolean function constructed by Ambainis and Sun [3]. This implies that there cannot exist a Boolean function admitting the normalized block property, the transitive property and the 2-mixing property which has a better separation between block sensitivity and sensitivity than the function constructed by Ambainis and Sun [3].

**► Theorem 16.** Any Boolean function admitting the normalized block property, the transitive property, the 2-mixing property and which depends on at least two variables has $3bs \le 2s^2 - s$.

The proof of the above theorem is in the full version. In a previous version of this paper, we did not assume that the number of dependent variables is at least two. However, as Krišjānis Prusis and Andris Ambainis pointed out to us, there was a small error in the proof and indeed the univariate function $f(x) = x$ does not satisfy this inequality ($s = bs = 1$). Moreover, they noticed that, as the 2-mixing property implies $s_1 = d_\wedge = c_1$ (cf. Lemma 13 and the following remark), their result [2] directly implies that any Boolean function admitting the 2-mixing property satisfies $3bs \le 2s^2 + s$.

Our main result is to get rid of the dependence on the transitive property and the mixing
property. Imposing only the normalized block property on DNFs is a weak restriction as there
is no constraint on $\bar{A}_i$. Further, given the DNF in compact form representation admitting the
normalized block property is a natural way to represent the function through its (maximal)
block sensitivity complexity. We show the following theorem concerning Boolean functions
admitting block property:

**► Theorem 17.** Any Boolean function admitting the block property has $bs_0 \le 4s^2$. In particular, if the representation is normalized, $bs \le 4s^2$.

The importance of the result is that the block property seems to be a quite natural
restriction for studying the relations between the sensitivity and the block sensitivity. In
fact, by assuming that the block sensitivity is maximized, by the blocks $B_i$, on the all zeros
inputs with $f(0^n) = 0$ (which is always possible), the block property intuitively asserts the
output is one if from the all zeros input, we can get an input in $f^{-1}(1)$ only by flipping at
least one of the blocks $B_i$. If it is not the case, it would mean there are other non-disjoint
blocks which are present just for diminishing the sensitivity.

Before presenting the proof, we prove three lemmas, after which the above result follows
immediately.

**► Lemma 18.** Any Boolean function $f$ admitting the block property has $bs_0 = d_\vee$.

**Proof.** From Definition 6a, we have that $f(0^n) = 0$ and thus we have that every $A_i$ is non-empty. Now, it is easy to see that $bs_0 \ge bs(f, 0^n) \ge d_\vee$ – choose each $A_i$ as a block. Any two blocks are disjoint because of the block property and by flipping any of the blocks, one of the AND gates will evaluate to 1.
15:8 On the Sensitivity Conjecture for Disjunctive Normal Forms

From Definition 6b, we know that the maximum 0-block sensitivity is attained on $0^n$. Let the sensitive blocks for which it attains maximum 0-block sensitivity be $B_1, \dots, B_k$. Thus when some $B_i$ is flipped to all 1s, at least one of the AND gates evaluates to 1. Since the blocks are disjoint, we can associate a distinct AND gate to each sensitive block. Therefore the number of sensitive blocks is at most the number of AND gates, i.e., $\mathbf{bs}_0 = k \le d_\vee$. ◀

**Lemma 19.** Any Boolean function admitting the block property has $s \ge \left\lfloor \frac{d_\vee}{2d_\wedge - 1} \right\rfloor$.

The previous lemma is easily seen as optimal by a multiplicative factor two by considering
the OR function.

**Proof.** Let $E$ be a subset of AND gates such that for any two $\wedge_i, \wedge_j \in E$, we have $A_i \cap \bar{A}_j = \emptyset$ and $A_j \cap \bar{A}_i \neq \emptyset$. Let $P = \bigcup_{\wedge_i \in E} P_i$, where $P_i$ is an arbitrarily chosen subset of $A_i$ of size $|A_i| - 1$ (note that $|A_i| \ge 1$ as otherwise we would have $f(0^n) = 1$, contradicting Definition 6a). Consider $a \in \{0, 1\}^n$, where $a_i = 1$ if and only if $x_i \in P$. We observe that for all $\wedge_i \in E$, $\wedge_i(a) = 0$. Also, for all $\wedge_i \notin E$, we have that $A_i \cap P = \emptyset$ from the block property, and therefore $\wedge_i(a) = 0$. In short, $f(a) = 0$. Now for any $\wedge_i \in E$, let $x_{q(i)} \in A_i \setminus P_i$. Since $\wedge_i(a^{q(i)}) = 1$, we have that $s_0(f, a) \ge |E|$.

Now, we will prove that there is a set $E$ such that $|E| \ge \left\lfloor \frac{d_\vee}{2d_\wedge - 1} \right\rfloor$. Let $G$ be a directed graph on $d_\vee$ vertices where the $i^{th}$ vertex corresponds to $\wedge_i$. We have a directed edge from vertex $i$ to vertex $j$ if $\bar{A}_i \cap A_j \neq \emptyset$. Let $U(G)$ be $G$ with orientation on the edges removed. Consider the following procedure for constructing $E$:

(1) Include to $E$, the AND gate corresponding to the vertex with the smallest degree in $U(G)$.

(2) Remove the vertex picked in (1) and all its in-neighbors and out-neighbors from $G$.

(3) Repeat (1) if $G$ is not empty.

From block property, we have that the out-degree of vertex $i$ in $G$ is at most $|\bar{A}_i|$. Thus the total number of edges in $G$ is at most $\sum_{i \in [d_\vee]} |\bar{A}_i| \le d_\vee(d_\wedge - 1)$. This implies that the sum of the degree of all vertices in $U(G)$ is at most $2d_\vee(d_\wedge - 1)$. Therefore, there exists a vertex in $U(G)$ of degree at most $2d_\wedge - 2$. By including the corresponding AND gate into $E$, the number of vertices in $G$ reduces by at most $2d_\wedge - 1$. In order for $G$ to be empty, there should be at least $\left\lfloor \frac{d_\vee}{2d_\wedge - 1} \right\rfloor$ iterations of the above procedure, and since cardinality of $E$ grows by 1 after each iteration, we have that $|E| \ge \left\lfloor \frac{d_\vee}{2d_\wedge - 1} \right\rfloor$.

Therefore, we have $s \ge s_0(f, a) \ge |E| \ge \left\lfloor \frac{d_\vee}{2d_\wedge - 1} \right\rfloor$.

<figure><img src="image_3.png" /></figure>

**Lemma 20.** Any Boolean function admitting the block property has $s \ge \left\lfloor \frac{d_\wedge}{2} \right\rfloor$.

**Proof.** If $s_1 \ge \left\lfloor \frac{1+d_\wedge}{2} \right\rfloor$, we are done. Therefore, we can assume $s_1 < \left\lfloor \frac{1+d_\wedge}{2} \right\rfloor$. Let $i^* = \operatorname*{argmax}_i d_{\wedge i}$. Consider $a \in \{0,1\}^n$ with $a_j = 1$ if and only if $x_j \in A_{i^*}$. We note that $\wedge_{i^*}(a) = 1$ and $|a|$ (Hamming weight of $a$) is nonzero since $A_{i^*}$ is nonempty from Definition 6a.

Let $x_j \in A_{i^*}$. We claim that $f(a^j) = 0$. The proof is by contradiction. Suppose, $f(a^j) = 1$. It is clear that $\wedge_{i^*}(a^j) = 0$ as $x_j \in A_{i^*}$. Thus, there must exist some $k \neq i^*$, such that $\wedge_k(a^j) = 1$. From block property, we know that $A_{i^*} \cap A_k = \emptyset$, but all variables assigned to 1 in $a^j$ are in $A_{i^*}$. This implies $A_k = \emptyset$. Therefore $\wedge_k(0^n) = 1$, contradicting Definition 6a.

Now we would like to claim that for any $x_j \in A_{i^*}$, we have $s_0(f, a^j) \ge 1 + \lfloor \frac{d_\wedge}{2} \rfloor$. We first note that $s_1(f, a) < \lfloor \frac{1+d_\wedge}{2} \rfloor$ and since for any $x_j \in A_{i^*}$, we have $f(a^j) = 0$, we have
that $|A_{i*}| < \lfloor \frac{1+d_{\Delta}}{2} \rfloor$. Let $D = \{x_p \in \bar{A}_{i*} | f(a^p) = 1\}$. Since, $\mathbf{s}_1(f, a) < \lfloor \frac{1+d_{\Delta}}{2} \rfloor$, this implies $|\bar{A}_{i*}| - |D| + |A_{i*}| < \lfloor \frac{1+d_{\Delta}}{2} \rfloor$ or equivalently, $|D| > \lfloor \frac{d_{\Delta}}{2} \rfloor - 1$. Fix $x_p \in D$ and $x_j \in A_{i*}$. Since $f(a^p) = 1$, we know there exists some $k \neq i^*$, such that $\wedge_k(a^p) = 1$. By block property, we know that $x_j \notin A_k$, and this implies $f(a^{\{j,p\}}) = 1$. Thus, we have that for any fixed $x_j \in A_{i*}$, $\mathbf{s}_0(f, a^j) \ge |D| + 1$ as for every $x_p \in D$, we have $f(a^{\{j,p\}}) = 1$ and also $f(a) = 1$. Therefore, for every $x_j \in A_{i*}$ we have $\mathbf{s}_0(f, a^j) \ge |D| + 1 > 1 + \lfloor \frac{d_{\Delta}}{2} \rfloor - 1 = \lfloor \frac{d_{\Delta}}{2} \rfloor$.

Therefore, we have that either $\mathbf{s}_1$ or $\mathbf{s}_0$ is at least $\lfloor \frac{d_{\Delta}}{2} \rfloor$.

<figure><img src="image_4.png" /></figure>

**Proof of Theorem 17.** From Lemma 19 and Lemma 20, we have that for any Boolean function admitting the block property $\mathbf{s}^2 > \frac{d_{\vee}}{4}$. Combining this with Lemma 18, we have that $4\mathbf{s}^2 > \mathbf{bs}_0$.

<figure><img src="image_5.png" /></figure>

We can notice that Lemma 20 is optimal, i.e., we give an example of a Boolean function admitting the block property with $\mathbf{s}_0 = \mathbf{s}_1 = \lfloor d_{\wedge}/2 \rfloor$. The set of variables is $X = \{x_1, \dots, x_{2n+1}\}$. We describe the example by its $\wedge$-gates $\wedge_1, \dots, \wedge_{n+1}$: for all $i \in [n]$, $A_i = \{x_{2i}\}$, $\bar{A}_i = \emptyset$, $A_{n+1} = \{x_{2i-1} | i \in [n+1]\}$ and $\bar{A}_i = \{x_{2i} | i \in [n]\}$.

Finally, we conclude with an absolute lower bound on the sensitivity of functions admitting block property.

**Corollary 21.** Let $f$ be a Boolean function which depends on $n$ variables. If $f$ admits the block property, then $2\mathbf{s}(f) \ge n^{1/3}$.

**Proof.** The number of variables which appear in the DNF is at most $d_{\vee}d_{\wedge}$, and so $d_{\vee}d_{\wedge} \ge n$. By Lemma 19 and Lemma 20,

$$ \mathbf{s}^3 \ge \left( \frac{d_{\vee}}{2d_{\wedge}} \right) \left( \frac{d_{\wedge}}{2} \right)^2 \ge \frac{d_{\vee}d_{\wedge}}{8} \ge \frac{n}{8}. $$

<figure><img src="image_6.png" /></figure>

## 3.1 t-Block Property

In this subsection, we extend the notion of block property to t-block property as follows.

**Property 22 (t-Block property).** A Boolean function is said to admit the t-block property if under a compact form representation $\forall x \in X$, we have $|\{A_i|x \in A_i\}| \le t$.

We have that 1-block property is exactly the same as block property discussed in the previous subsection. Let us notice that the notion of t-block property is far more general than the one of read-t DNF presented in [4] since, here only the number of times where the variables appear positively is bounded.

First, we show an upper bound on Boolean functions admitting the t-block property in terms of the size of the DNF. The proof is very similar to the one for Lemma 18 and can be found in the full paper.

**Lemma 23.** Any Boolean function $f$ admitting the t-block property has $\mathbf{bs}_0 \le d_{\vee}$.

Next, we prove a lower bound on Boolean functions admitting the t-block property in terms of t, the width of the DNF, and the size of the DNF.

**Lemma 24.** If $f$ admits the t-block property, then $\mathbf{s} \ge \lfloor \frac{d_{\vee}}{3td_{\wedge} - 2t - d_{\wedge} + 1} \rfloor$.

**Proof.** Let $E$ be a subset of AND gates such that for any two $\wedge_i, \wedge_j \in E$, we have $(A_i \cup \bar{A}_i) \cap A_j = \emptyset$. Let $A = \bigcup_{\wedge_i \in E} A_i$ (note that any $|A_i| \ge 1$ as otherwise we would have $f(0^n) = 1$,
15:10 On the Sensitivity Conjecture for Disjunctive Normal Forms

contradicting Definition 6a). Consider $\mathcal{A}$ the set of 0-vectors with support in $\mathcal{A}$. More formally, $\mathcal{A} = \{a \in \{0,1\}^n \mid f(a) = 0 \text{ and } \forall i, a_i = 1 \implies x_i \in \mathcal{A}\}$.

First notice that $0^n \in \mathcal{A}$, so this set is not empty. Let $\bar{a}$ be an element of $\mathcal{A}$ with maximal Hamming weight. For any $\wedge_i \in \mathcal{E}$, the gate $\wedge_i$ does not depend on the variables in $(\mathcal{A} \setminus \mathcal{A}_i)$ by definition of $\mathcal{E}$ and $\mathcal{A}$. So, $f(\bar{a}) = 0$ implies that there exists a variable $x_{l_i} \in \mathcal{A}_i$ such that $\bar{a}_{l_i} = 0$. Then, by maximality of Hamming weight of $\bar{a}$, $f(\bar{a}^{l_i}) = 1$ and so $\bar{a}$ is 0-sensitive on $l_i$. Finally, for all $i, j \in \mathcal{E}$ the indices $l_i$ and $l_j$ are distinct since $\mathcal{A}_i \cap \mathcal{A}_j = \emptyset$. Consequently, we have that $\mathfrak{s}_0(f, \bar{a}) \ge |\mathcal{E}|$.

Now, we will prove that there is a set $\mathcal{E}$ such that $|\mathcal{E}| \ge \left\lfloor \frac{d_\vee}{3td_\wedge - 2t - d_\wedge + 1} \right\rfloor$. Let $\mathcal{G}$ be a directed graph on $d_\vee$ vertices where the $i^{th}$ vertex corresponds to $\wedge_i$. We have a directed edge from vertex $i$ to vertex $j$ if $\bar{A}_i \cap \mathcal{A}_j \neq \emptyset$. Let $\mathcal{U}(\mathcal{G})$ be $\mathcal{G}$ with orientation on the edges removed. Consider the following procedure for constructing $\mathcal{E}$:

(1) Add to $\mathcal{E}$, the AND gate corresponding to the vertex with the smallest degree in $\mathcal{U}(\mathcal{G})$.

(2) Remove the vertex picked in (1) and all its in-neighbors and out-neighbors from $\mathcal{G}$.

(3) Remove any vertex from $\mathcal{G}$ associated with a gate $\wedge_j$ with $\mathcal{A}_i \cap \mathcal{A}_j \neq \emptyset$.

(4) Repeat from (1) if $\mathcal{G}$ is not empty.

From $t$-block property, we have that the out-degree of vertex $i$ in $\mathcal{G}$ is at most $t|\bar{A}_i|$. Thus the total number of edges in $\mathcal{G}$ is at most $\sum_{i \in [d_\vee]} t|\bar{A}_i| \le td_\vee(d_\wedge - 1)$. This implies that the sum of the degree of all vertices in $\mathcal{U}(\mathcal{G})$ is at most $2td_\vee(d_\wedge - 1)$. Therefore, there exists a vertex in $\mathcal{U}(\mathcal{G})$ of degree at most $2td_\wedge - 2t$. By including the corresponding AND gate into $\mathcal{E}$, the number of vertices in $\mathcal{G}$ reduces by at most $2td_\wedge - 2t + 1$ at step (2). Moreover, at step (3), by the $t$-block property, there are at most $(t-1)|\mathcal{A}_i| \le td_\wedge - d_\wedge$ gates $\wedge_j$ such that $\mathcal{A}_i \cap \mathcal{A}_j \neq \emptyset$ and $j \neq i$. Consequently at most $3td_\wedge - 2t - d_\wedge + 1$ gates are removed at each step. In order for $\mathcal{G}$ to be empty, there should be at least $\left\lfloor \frac{d_\vee}{3td_\wedge - 2t - d_\wedge + 1} \right\rfloor$ iterations of the above procedure, and since cardinality of $\mathcal{E}$ grows by 1 after each iteration, we have that $|\mathcal{E}| \ge \left\lfloor \frac{d_\vee}{3td_\wedge - 2t - d_\wedge + 1} \right\rfloor$.

Therefore, we have $\mathfrak{s} \ge \mathfrak{s}_0(f, a) \ge |\mathcal{E}| \ge \left\lfloor \frac{d_\vee}{3td_\wedge - 2t - d_\wedge + 1} \right\rfloor$.

<figure><img src="image_7.png" /></figure>

As a corollary, we obtain the following.

**Corollary 25.** Let $\mathfrak{f}$ be a Boolean function admitting the $t$-block property, with $t \le d_\vee d_\wedge^{-1-\epsilon}$, for some $\epsilon > 0$. Then, $\mathfrak{bs}_0(f) \le t (3\mathfrak{s}(f))^{1+\frac{1}{\epsilon}}$.

**Proof.** Since $t \le d_\vee d_\wedge^{-1-\epsilon}$, we have that $d_\wedge \le (\frac{d_\vee}{t})^{1/(1+\epsilon)}$. Substituting in Theorem 24, we have that $\mathfrak{s}(f) \ge \frac{d_\vee}{3t(d_\vee/t)^{1/(1+\epsilon)}}$. After rearranging and simplifying, we get $t^\epsilon (3\mathfrak{s}(f))^{1+\epsilon} \ge (d_\vee)^\epsilon$. We substitute Lemma 23, and simplify to obtain $t (3\mathfrak{s}(f))^{1+\frac{1}{\epsilon}} \ge \mathfrak{bs}_0(f)$. $\blacksquare$

4 Low Sensitivity Boolean functions

Gopalan et al. [11] show that functions with low sensitivity have concise descriptions, so consequently the number of such functions is small. Indeed, they show that knowing the values on a Hamming ball of radius $2\mathfrak{s} + 1$ suffices. More precisely,

**Theorem 26 (Gopalan et al. [11]).** Let $\mathfrak{f}$ be a Boolean function of sensitivity $\mathfrak{s}$. Then, it is uniquely specified by its values on any ball of radius $2\mathfrak{s}$.

We extend their observation to a more general one:
**Theorem 27.** Let $f$ and $g$ be two Boolean functions. If $f$ and $g$ coincide on a ball of radius $\mathbf{s}(f) + \mathbf{s}(g)$ then, $f = g$.

Before we prove Theorem 27, we note the following handy lemma:

**Lemma 28.** Let $f$ and $g$ be two Boolean functions. We have $\mathbf{s}(f \oplus g) \le \mathbf{s}(f) + \mathbf{s}(g)$ and $\mathbf{bs}(f \oplus g) \le \mathbf{bs}(f) + \mathbf{bs}(g)^2$.

**Proof.** For any $x \in \{0,1\}^n$ and $i \in [n]$, if $(f \oplus g)(x) \ne (f \oplus g)(x^i)$ then we have that either $f(x) \ne f(x^i)$ or $g(x) \ne g(x^i)$. This implies, for every $x \in \{0,1\}^n$, $\mathbf{s}(f \oplus g, x) \le \mathbf{s}(f, x) + \mathbf{s}(g, x)$. Similarly, for any $x \in \{0,1\}^n$ and $B \subseteq [n]$, if $(f \oplus g)(x) \ne (f \oplus g)(x^B)$ then we have that either $f(x) \ne f(x^B)$ or $g(x) \ne g(x^B)$. This implies, for every $x \in \{0,1\}^n$, $\mathbf{bs}(f \oplus g, x) \le \mathbf{bs}(f, x) + \mathbf{bs}(g, x)$. ◀

**Proof of Theorem 27.** The proof is by contradiction. Suppose there exists $a \in \{0,1\}^n$ such that for every $r \in \{0,1\}^n$ of hamming weight at most $\mathbf{s}(f) + \mathbf{s}(g)$, we have that $f(a \oplus r) = g(a \oplus r)$. This implies that for every $r \in \{0,1\}^n$ with $||r|| \le \mathbf{s}(f) + \mathbf{s}(g)$, we have $(f \oplus g)(a \oplus r) = 0$. Consider $x \in \{0,1\}^n$ of the smallest hamming distance from $a$ such that $(f \oplus g)(x) = 1$. If such a $x$ does not exist then it implies that $f \oplus g$ is the constant zero function. In that case we have that $f = g$, a contradiction. Therefore, let us suppose that $x$ exists as described above. Let $d$ be the hamming distance between $x$ and $a$. We know that $d > \mathbf{s}(f) + \mathbf{s}(g)$. Additionally, we know that there are exactly $d$ neighbors of $x$ at hamming distance $d-1$ from $a$. Since, $x$ was the input with the smallest distance from $a$ such that $(f \oplus g)(x) = 1$, we know that the $d$ neighbors of $x$ at hamming distance $d-1$ from $a$ all evaluate to 0 on $(f \oplus g)$. This means that $\mathbf{s}(f \oplus g, x) \ge d > \mathbf{s}(f) + \mathbf{s}(g)$, which is a contradiction following Lemma 28. ◀

Next, we explore the tightness of Theorem 27.

**Proposition 29.** For every $p, q \in \mathbb{N}$, greater than 1, there exists Boolean functions $f$ and $g$ such that $\mathbf{s}(f) = p$, $\mathbf{s}(g) = q$, and $f$ and $g$ coincide on a ball of radius $\mathbf{s}(f) + \mathbf{s}(g) - 1$.

**Proof.** Without loss of generality we will assume that $p \le q$. Fix $p$ and $q$. We will build two function $f$ and $g$ on $p+q$ variables. Let $a \in \{0,1\}^{p+q}$ be a special input defined as follows: $\forall i \in [p+q], a_i = 1$ if and only if $i = 1$, or $i > 2p$, or $i \ne 2p$ is even. Now we define $f$ and $g$ as follows:

$$f(x_1, \dots, x_{p+q}) = \begin{cases} 0 & \text{if } \sum_{i=1}^{2p} x_i < p \\ 1 & \text{if } \sum_{i=1}^{2p} x_i > p \\ \sum_{\substack{j=1, \\ j \le 2p}}^{p} j \bmod 2 & \text{if } \sum_{i=1}^{p} x_i = p \end{cases} \qquad g(x) = \begin{cases} 0 & \text{if } x = a \\ f(x) & \text{otherwise.} \end{cases}$$

Now, we will show that $\mathbf{s}(f) = p$. Fix $x \in \{0,1\}^{p+q}$. $x$ is not sensitive on the last $q-p$ coordinates. If $\sum_{i=1}^{2p} x_i < p-1$ or $\sum_{i=1}^{2p} x_i > p+1$ then $\mathbf{s}(f,x) = 0$. If $\sum_{i=1}^{2p} x_i = p$ then $\mathbf{s}(f,x) = p$. If $\sum_{i=1}^{2p} x_i = p-1$ then $\mathbf{s}(f,x) \le p$. This is because for any subset of $[2p]$ of size $p+1$ there is both an odd number and an even number in the subset (by pigeonhole principle), and thus amongst its $p+1$ neighbors of hamming weight $p$ (in the first $2p$ coordinates) there

<footnote n="2">² $\forall x \in \{0,1\}^n, (f \oplus g)(x) = f(x) \oplus g(x)$.</footnote>
15:12 On the Sensitivity Conjecture for Disjunctive Normal Forms

must be a neighbor which is not sensitive w.r.t. $x$. Similarly, we have that if $\sum_{i=1}^{2p} x_i = p+1$ then $\mathbf{s}(f, x) \le p$.

Next, we will show that $\mathbf{s}(g) = q$. Fix $x \in \{0, 1\}^{p+q}$. If $x$ is not in the hamming ball of radius 1 centered at $a$ then, $\mathbf{s}(g, x) = \mathbf{s}(f, x) \le p \le q$. If $x = a$ then, it is sensitive on all the last $q-p$ coordinates and has $p$ sensitive neighbors in the first $2p$ coordinates. Thus, $\mathbf{s}(g, a) = q$. If $x$ is a neighbor of $a$ through one of the last $q-p$ coordinates (i.e., assuming $q-p > 0$) then $\mathbf{s}(g, x) = p+1 \le q$. If $x$ is a neighbor of $a$ through one of the first $2p$ coordinates then, we can assume $g(x) = 1$. This means hamming weight of $x$ in first $2p$ coordinates is $p+1$ and we know that it is not sensitive on the last $q-p$ coordinates. From the definition of $a$, we know that there is at least one neighbor of $x$ of hamming weight $p$ in the first $2p$ coordinates such that its value on $g$ is the same as $g(x)$. Therefore $\mathbf{s}(g, x) \le p \le q$.

Finally, we claim that $f$ and $g$ coincide on the ball of radius $p+q-1$ centered at $(a \oplus \vec{1})$ (follows from the construction of $g$). This completes the proof as $f$ and $g$ are distinct $(f(a) \neq g(a))$ and to distinguish between them by a ball centered at $(a \oplus \vec{1})$, we need to consider a ball of radius $p+q$. $\quad$

In the case of monotone Boolean functions, we can improve upon the results in Theorem 26 and Theorem 27 as follows: any monotone Boolean function $f$ is uniquely specified by its values on the ball of radius $\mathbf{s}$ centered at $0^n$. This is because, for any input $x$ of hamming weight greater than $\mathbf{s}(f)$, $f(x)$ is equal to 1 if at least one of its neighbors of hamming weight $|x| - 1$ is evaluated to 1 on $f$. In other words,

$$f(x) = \bigvee_{\substack{y=x \oplus e_i \\ |y|=|x|-1}} f(y).$$

Furthermore, this result is tight because Wegener's monotone Boolean function [20] $f$ of sensitivity $\frac{1}{2}\log n + \frac{1}{4}\log \log n + \mathcal{O}(1)$ is identical to the constant zero function on the ball of radius $\mathbf{s}(f) - 1$ centered at $0^n$.

5 The Sensitivity Conjecture: A Computational Perspective

We would like to briefly discuss in this section a new perspective on the sensitivity conjecture. Consider a strong version of the sensitivity conjecture which was suggested by Nisan and Szegedy [16]: for every Boolean function $f$, we have $\mathbf{bs}(f) \le c \cdot \mathbf{s}(f)^2$, for some constant $c$. Let us assume that the above conjecture is true. We note here that there is no evidence or reason to refute this strong version of the sensitivity conjecture. Now consider a computational problem called the sensitivity problem defined based on this assumption.

► **Definition 30 (Sensitivity Problem).** Given a circuit $C: \{0,1\}^n \to \{0,1\}$, $x \in \{0,1\}^n$, and blocks $B_1, \dots, B_k$, the sensitivity problem is to find $y \in \{0,1\}^n$ such that $\mathbf{s}(C, y) \ge \sqrt{\mathbf{bs}(C, x, B_1, \dots, B_k)/c}$.

A solution to the sensitivity problem is guaranteed to exist and a solution can be verified in poly($n$) time, thus the problem is in **TFNP**. We wonder if the proof of the sensitivity conjecture would give us an efficient algorithm to solve this problem in **P**?

We investigated the proofs of the sensitivity conjecture for restricted classes of Boolean functions that exist in literature. In each of these proofs we indeed find an efficient algorithm to solve the above problem in **P**. For instance, consider the class of Boolean functions admitting the normalized block property. In this case, the computational problem would be that given a DNF $\Phi$, $x \in \{0,1\}^n$, and blocks $B_1, \dots, B_k$, find $y \in \{0,1\}^n$ such that
$s(\Phi, y) \ge \sqrt{bs(\phi, x, B_1, ..., B_k)/2}$ or find two clauses in $\Phi$ which violate $\Phi$ admitting the block property. This problem like the sensitivity problem is in **TFNP**. However, the proof of Lemma 19 gives us an efficient algorithm to find an input $a_1$ with sensitivity $\left\lceil \frac{d_\vee}{2d_\wedge - 1} \right\rceil$ and the proof of Lemma 20 gives us an efficient algorithm to find an input $a_2$ with sensitivity $\left\lceil \frac{d_\wedge}{2} \right\rceil$. Since, $bs(\phi, x, B_1, ..., B_k) \le bs(\Phi) = d_\vee$, either $a_1$ or $a_2$ is a solution to our problem (assuming there is no violation to the block property of $\Phi$). Thus the computational problem in the case of functions admitting the block property is in **P**.

Similarly, for every monotone function $f$, and every input $x$ we have $s(f, x) = bs(f, x)$ [15]. Therefore, for the computational version of the sensitivity problem adapted to the monotone restriction, the input $x$ will be a trivial solution and thus the computational problem would be in **P**. Finally, even for the case of min-term transitive functions, we have an efficient algorithm implicit in the proof of Chakraborthy [6] who showed that for any min-term transitive function $f$, $bs(f) \le 2s(f)^2$.

Returning to ponder on the existence of efficient algorithms for the sensitivity problem, while it is related to the sensitivity conjecture, it is possible that the sensitivity conjecture is true but there is no efficient algorithm for the sensitivity problem. Similarly, it is possible that an efficient algorithm for the sensitivity problem is found without resolving the sensitivity conjecture (in this case the sensitivity problem should be considered to be in **NP** and not in **TFNP**). However, our progress on the sensitivity conjecture under various restricted settings seem to be by finding a vertex of high sensitivity by starting from a given input with high block sensitivity. Therefore, studying various restrictions on models of computations for Boolean functions seems to be the right direction to pursue, in order to make progress on the sensitivity conjecture.

**6 Conclusion**

In this paper, we motivate the study of the sensitivity conjecture through restrictions on a model of computation. In this regard, we introduced a structural restriction on DNFs representing Boolean functions called the normalized block property. We showed that the examples of Boolean functions that are popular in literature for having a quadratic separation between sensitivity and block sensitivity admit this property. More importantly, we showed that the sensitivity conjecture is true for the class of Boolean functions admitting the normalized block property. Furthermore, we extended a result of Gopalan et al. [11] and also provided matching lower bounds for our results. Finally, we motivated a new computational problem about finding an input with (relatively) high sensitivity, with respect to the block sensitivity for a given input.

**Acknowledgements.** We would like to thank Satya Lokam for discussions and encouraging us to work on the sensitivity conjecture. In particular, Karthik would like to thank him for the internship at Microsoft Research. We would like to thank Avishay Tal for pointing out Corollary 21. We would like to thank Roei Tell for motivation and discussions. We would like to thank Andris Ambainis and Krišjānis Prūsis for pointing out an error in a first version of Theorem 16 and for highlighting the relation between this theorem and the result in [2]. Finally, we would like to thank the anonymous reviewers for helping us improve the presentation of the paper.
References

1 Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaomiing Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In *Automata, Languages, and Programming – 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I*, pages 101–113, 2014. doi: 10.1007/978-3-662-43948-7_9.

2 Andris Ambainis and Krisjanis Prusis. A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity. In *Mathematical Foundations of Computer Science 2014 – 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II*, pages 33–44, 2014. doi:10.1007/978-3-662-44465-8_4.

3 Andris Ambainis and Xiaomiing Sun. New separation between $s(f)$ and $bs(f)$. *Electronic Colloquium on Computational Complexity (ECCC)*, 18:116, 2011. URL: http://eccc.hpi-web.de/report/2011/116.

4 Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the sensitivity conjecture for read-k formulas. In *41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 – Kraków, Poland*, pages 16:1–16:14, 2016. doi:10.4230/LIPIcs.MFCS.2016.16.

5 Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. *Theor. Comput. Sci.*, 288(1):21–43, 2002. doi:10.1016/S0304-3975(01)00144-X.

6 Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. *Discrete Mathematics & Theoretical Computer Science*, 13(4):51–60, 2011.

7 Stephen A. Cook and Cynthia Dwork. Bounds on the time for parallel ram's to compute simple functions. In *Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA*, pages 231–233, 1982. doi:10.1145/800070.802196.

8 Stephen A. Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. *SIAM J. Comput.*, 15(1):87–97, 1986. doi:10.1137/0215006.

9 Andrew Drucker. Block sensitivity of minterm-transitive functions. *Theor. Comput. Sci.*, 412(41):5796–5801, 2011. doi:10.1016/j.tcs.2011.06.025.

10 Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some boolean function complexity measures. In *2013 IEEE Conference on Computational Complexity*, pages 185–196. IEEE, 2013.

11 Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, and Avi Wigderson. Smooth boolean functions are easy: Efficient algorithms for low-sensitivity functions. In *Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016*, pages 59–70, 2016. doi:10.1145/2840728.2840738.

12 Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. *Theory of Computing, Graduate Surveys*, 4:1–27, 2011. doi:10.4086/toc.gs.2011.004.

13 Claire Kenyon and Samuel Kutin. Sensitivity, block sensitivity, and l-block sensitivity of boolean functions. *Inf. Comput.*, 189(1):43–53, 2004. doi:10.1016/j.ic.2002.12.001.

14 Chengyu Lin and Shengyu Zhang. Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. *CoRR*, abs/1602.06627, 2016. URL: http://arxiv.org/abs/1602.06627.

15 Noam Nisan. CREW prams and decision trees. *SIAM J. Comput.*, 20(6):999–1007, 1991. doi:10.1137/0220062.

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 David Rubinstein. Sensitivity vs. block sensitivity of boolean functions. *Combinatorica*, 15(2):297-299, 1995. doi:10.1007/BF01200762.

18 Xiaoming Sun. Block sensitivity of weakly symmetric functions. *Theor. Comput. Sci.*, 384(1):87-91, 2007. doi:10.1016/j.tcs.2007.05.020.

19 Madars Virza. Sensitivity versus block sensitivity of boolean functions. *Inf. Process. Lett.*, 111(9):433-435, 2011. doi:10.1016/j.ipl.2011.02.001.

20 Ingo Wegener. The critical complexity of all (monotone) boolean functions and monotone graph properties. *Information and Control*, 67(1-3):212-222, 1985. doi:10.1016/S0019-9958(85)80036-X.