# On the Sensitivity Conjecture for Read-k Formulas

Mitali Bafna, Satyanarayana V Lokam, Sébastien Tavenas, Ameya Velingker

► To cite this version:

Mitali Bafna, Satyanarayana V Lokam, Sébastien Tavenas, Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Aug 2016, Krakow, Poland. 10.4230/LIPIcs.MFCS.2016.16 . hal-02447411

HAL Id: hal-02447411

https://hal.science/hal-02447411

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 Read-k Formulas

Mitali Bafna*¹, Satyanarayana V. Lokam², Sébastien Tavenas³, and Ameya Velingker*⁴

1. Indian Institute of Technology, Madras, Chennai, India
   mitali.bafna@gmail.com

2. Microsoft Research, Bangalore, India
   satya@microsoft.com

3. Microsoft Research, Bangalore, India
   t-sebat@microsoft.com

4. Carnegie Mellon University, Pittsburgh, USA
   avelingk@cs.cmu.edu

## Abstract

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over $ℝ$, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the “missing link”.

Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and functions describing graph properties.

In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.

**1998 ACM Subject Classification** F.1.3 Relations among complexity measures

**Keywords and phrases** sensitivity conjecture, read-k formulas, analysis of Boolean functions

**Digital Object Identifier** 10.4230/LIPIcs.MFCS.2016.16

## 1 Introduction

Sensitivity and block sensitivity are two important complexity parameters of Boolean functions. The sensitivity conjecture states that these two parameters are polynomially related. A long-standing open question is to prove (or disprove) this conjecture. In this paper, we prove the conjecture for several subclasses of functions computable by read-k formulas.

The sensitivity $s(f)$ of a Boolean function $f$ is the maximum (over all inputs) number of coordinate dimensions along which the value of the function changes. This notion was

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

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

<footnote>* This work was done while the author was an intern at Microsoft Research, Bangalore, India.</footnote>
16:2 Sensitivity Conjecture for Read-k Formulas

first introduced by Cook et al. [9] to prove lower bounds on the parallel complexity (in the CREW PRAM model) of Boolean functions. Nisan [16] introduced the more general definition of block sensitivity. The block sensitivity $bs(f)$ of a Boolean function $f$ is the maximum (again, over all inputs) number of disjoint subsets of coordinate dimensions such that flipping all values of a given input in any of these subsets results in flipping the value of the function. Nisan proved that block sensitivity asymptotically captures the CREW PRAM complexity of all Boolean functions. Remarkably, Nisan also showed that several other complexity parameters of Boolean functions such as certificate complexity, decision tree depth, and randomized decision tree depth are polynomially related to block sensitivity. Subsequently, Nisan and Szegedy [17] showed that block sensitivity and degree of polynomials (approximately) representing a Boolean function over $\mathbb{R}$ are polynomially related.

Hence, a number of combinatorial/algebraic parameters describing complexity of Boolean functions are all polynomially related to each other, but sensitivity has so far resisted such a polynomial equivalence with any of these other parameters. In fact, Nisan and Szegedy posed this as the sensitivity vs. block sensitivity question and since then, this question has come to be known as the “sensitivity conjecture”. More than two decades later, proving (or disproving) this conjecture still remains a foundational challenge in the study of Boolean functions. In recent times, this quest has become even more intriguing as other complexity parameters such as quantum query complexity (both exact and two-sided error versions) have been shown to be polynomially related to block sensitivity [5, 7]. At the same time, the sensitivity conjecture has been shown to be related to a number of other conjectures and open questions in Boolean function complexity, as illustrated in the survey [13].

The best known universal (applicable to all functions) upper bound on block sensitivity remains exponential in sensitivity [19] (see [14], [3], [21] for more refined upper bounds). In the other direction, Rubinstein [18] gives an example function where the gap between sensitivity and block sensitivity is quadratic (see [4] and references therein for improvements in constants). Thus the challenge is to close this gap between quadratic and exponential relations between block sensitivity and sensitivity.

Several approaches have been proposed in the literature to attack the sensitivity conjecture. Gotsman and Linial [12] showed that the degree vs. sensitivity problem is equivalent to a combinatorial problem on the maximum degree of induced subgraphs of the Boolean cube. Aaronson [1] (see also [6]) stated a problem about certain two-colorings of the integer lattice whose solution would imply the sensitivity conjecture. Recently, Gilmer et al. [10] formulated an approach to the degree vs. sensitivity problem using lower bounds on a two-party communication game. Even more recently, Gopalan et al. [11] prove an $l_2$-approximate version of the degree vs. sensitivity conjecture (the original one needs an $l_\infty$-approximation). They also formulate the notion of tree sensitivity and a robust analog of the degree vs. sensitivity conjecture.

To make progress on our understanding of this problem, researchers also studied the conjecture on special classes of Boolean functions. It is trivial to see that the conjecture holds for monotone functions and symmetric functions. A natural question, then, is if the sensitivity conjecture holds when the function is invariant under other groups of symmetries. Turán [22] proved that for Boolean functions that describe graph properties (edges are the Boolean variables) sensitivity is $\Omega(\sqrt{n})$ and hence the conjecture holds for graph properties. Chakraborty [8] studied minterm-transitive Boolean functions and showed that for such functions sensitivity is $\Omega(n^{1/3})$, thus showing the conjecture for this class of functions. Sun [20] studied block sensitivity for Boolean functions invariant under any transitive permutation group and showed that such functions must have block sensitivity $\Omega(n^{1/3})$.
**Our Results:** We prove the sensitivity conjecture for another restricted class of Boolean functions, namely certain functions computed by read-k formulas. A read-k formula is a tree whose internal nodes are Boolean gates, e.g., AND and OR, and leaves are literals of input variables with the restriction that each variable (as negated or non-negated literal) appears at most k times among the leaves. Such a formula computes a Boolean function in a natural way from the leaves to the root. A formula is called *regular* if all gates at a given depth are the same type and have the same fan-in.

In what follows, we will mainly focus on formulas composed of OR and AND gates. In particular we show that the sensitivity conjecture is true for read-log n regular formulas whose bottom fanins are sufficiently large.

**► Theorem 1.** Regular read-log n with large bottom fanin. Let $f$ be a Boolean function, dependent on $n$ variables, computed by a regular read-(log n) formula with bottom fan-in at least $\log^2 n$. Then $s(f) \ge \tilde{\Omega}(bs(f)^{1/4})$, where the $\tilde{\Omega}$ notation hides some logarithmic terms.

We would like to remove the condition on the bottom fanin. We succeed in doing so when the read and depth of the formula are constants.

**► Theorem 2.** Regular read-constant and constant depth. Let $f$ be computed by a regular read-k formula of depth-d for constants $k$ and $d$ such that all internal gates compute non-constant AND-OR functions. Then $s(f) = \Omega_{k,d}(\sqrt{bs(f))}$, where the hidden constant is a (rapidly decreasing) function of $k$ and $d$.

We present our main results (Theorem 1 and 2) on regular read-k formulas with AND and OR gates in Section 4. A crucial ingredient of our proofs is an application of the Lovász Local Lemma (LLL) to show that some literals can be assumed to occur in their positive form in such a formula without increasing the function's sensitivity and ensuring that any satisfying assignment of such a formula must have a large Hamming weight. However, in order to apply LLL, we need the bottom fan-in of such formulas to be large enough. So, we first prove the conjecture for formulas with large bottom fan-in. We then remove the restriction on the bottom fan-in by switching AND's of OR's to OR's of AND's (or vice versa). The idea is that if the formula is sufficiently large and the depth small, there has to be a layer $L$ with large fanin. Then, by switching, we expand the layers under $L$ and put $L$ close to the bottom.

When specialized to read-once formulas with symmetric gates or to read-k DNF's our lower bounds on regular read-k formulas yield better dependence on $k$.

**► Theorem 3.** Read-once with symmetric gates. Let $f$ be a Boolean function dependent on $n$ variables and computed by a read-once formula with symmetric gates. Then, $s(f) \ge \sqrt{n}$.

We note that Hiroki Morizumi [15] proved a similar lower bound for read-once AND-OR formulas.

**► Theorem 4.** Read-k DNF. Let $f$ be a Boolean formula dependent on $n$ variables and computed by a read-k DNF. Then $s(f) \ge n^{1/3}/(k+2)$. In particular, if $k \le n^{1/3-\epsilon} - 2$, then $s(f) \ge n^{\epsilon} \ge bs(f)^{\epsilon}$.

Our proof of the conjecture for read-once formulas with symmetric gates appears in Section 3. The results on DNF's appear in Section 5.
## 2 Notations and Preliminaries

- In this paper, log will always denote the logarithm to base two.

- We will always assume that $f$ is a Boolean function on $n$ variables and moreover that it depends on all its variables.

### 2.1 Measures on Boolean functions

Let $f: \{0,1\}^n \to \{0,1\}$ be a Boolean function. For $x \in \{0,1\}^n$ and $S \subseteq [n]$, we denote by $x^S$ the vector obtained by flipping all the coordinates on $x$ in $S$. For $x \in \{0,1\}^n$ and $z \in \{0,1\}$, we denote by $|x|_z$ the number of coordinates of $x$ with the value $z$.

- **Definition 5. Sensitivity:**

- The sensitivity of $f$ at $x$ is defined as the number of coordinates of $x$, which when flipped, will flip the value of $f$: $s(f,x) := |\{i \in [n] : f(x) \neq f(x^i)\}|$.

- For $z \in \{0,1\}$, the $z$-sensitivity of $f$ is defined as the maximum sensitivity of $f$ at an input in $f^{-1}(z)$: $s_z(f) := \max\{s(f,x) : f(x) = z\}$.

- Finally, the sensitivity of $f$ is the maximum sensitivity of $f$ among all inputs: $s(f) := \max\{s(f,x) : x \in \{0,1\}^n\} = \max\{s_0(f), s_1(f)\}$.

- **Definition 6.** The block sensitivity of $f$ at $x$, denoted $bs(f,x)$ is the maximum number of disjoint subsets $S_1, \dots, S_b$ of $[n]$ such that for every $i$, $f(x) \neq f(x^{S_i})$. The $z$-block sensitivity and block sensitivity of $f$ are defined similar to the case of sensitivity. In particular, $bs(f) := \max\{bs(f,x) : x \in \{0,1\}^n\}$.

- **Definition 7.** A certificate of $f$ on $x$ is a subset $S \subseteq [n]$ such that $f(y) = f(x)$ whenever $y_i = x_i, \forall i \in S$. The size of the certificate $S$ is $|S|$.

The certificate complexity of $f$ on $x$ denoted by $C(f,x)$ is the size of a smallest certificate of $f$ on $x$. The certificate complexity of $f$ denoted by $C(f)$ is $\max_x C(f,x)$. For $z \in \{0,1\}$, the $z$-certificate complexity of $f$ denoted by $C_z(f)$, is $\max_{x \in f^{-1}(z)} C(f,x)$.

We will use the following known results.

- **Lemma 8.** For any Boolean function $f$ and $z \in \{0,1\}$, $C_z(f) \geq bs_z(f) \geq s_z(f)$.

The first inequality above is from [16] and the second inequality is obvious from definitions.

- **Theorem 9 ([4]).** For any Boolean function $f$ and $z \in \{0,1\}$, $C_z(f) \geq \frac{3bs_{1-z}(f)}{2s_{1-z}(f)} - \frac{1}{2}$.

### 2.2 Formulas

- **Definition 10. Regular Read-k Formulas:**

- A formula $C$ is said to be $(a_1, \dots, a_d)$-regular if it is a layered tree of depth $d$ whose leaves are input variables or their negations and all internal nodes at a given layer $i$, $1 \le i \le d$, are gates of the same kind and the same fanin $a_i$. The layers are numbered 1 through $d+1$ from the root (output) to the leaves (inputs). We will often denote the gates at the layer $d$ by *bottom gates*. In this paper, we only consider both formulas of alternating layers of AND and OR gates (we could start at the root with either gate and then alternate) and formulas with symmetric gates.

- A formula is *read-k* if each variable (either in its negated or non-negated form) appears at most *k* times among its leaves.

One can argue that by replicating the arguments, we can always assume that the formula is in regular form. However, this idea does not work here because by doing this transformation, we would increase the read-multiplicity of the formula.
## 2.3 Lovász local lemma

We will make use of the Lovász Local Lemmas:

**Lemma 11.** [The Lovász Local Lemma: Symmetric Case] Let $A_1, \dots, A_n$ be events in an arbitrary probability space. Suppose that each event $A_i$ is mutually independent of a set of all the other events $A_j$ but at most $d$ and that $\Pr[A_i] \le p$ for all $1 \le i \le n$.

If $\Pr(d+1) < 1$, then $\Pr[\bigcap A_i] > 0$.

We will also use the general version of this lemma. Both versions can be found, e.g., in [2].

# 3 Read-once formulas with symmetric gates

In this section, we prove the sensitivity conjecture for read-once formulas with symmetric gates. The read-multiplicity is more restrictive than the model we will consider later but the gates we allow are more powerful.

**Definition 12.** Let $g$ be a non-constant symmetric function on $m$ inputs. We define $\tau(g)$ to be the minimal weight of an input $x \in \{0, 1\}^m$ such that $g(x) \ne g(\bar{0})$:

$$ \tau(g) := \min \{i \mid |x|_1 = i \implies g(x) \ne g(\bar{0})\}. $$

**Theorem 13.** Let $f$ be a Boolean function computed by a read-once formula $C$ with symmetric gates. Then, $s_0(f)s_1(f) \ge n$.

**Proof.** We prove it by induction on the depth of the formula $C$. If the depth of the formula is 1, then $f$ is a symmetric function on $n$ variables.

Let $z = f(\bar{0})$ and $t := \tau(f)$. By Definition 12, when $|x|_1 = t - 1$, $f(x) = z$ and when $|y|_1 = t$, $f(y) = 1 - z$. It follows immediately that $s_z(f, x) \ge n - t + 1$ and $s_{1-z}(f, y) \ge t$. So $s_0(f)s_1(f) \ge t(n - t + 1) \ge n$.

Now assume that the theorem is true for all depths $\le d$. We prove it for depth $d+1$.

So $f = h(g_1, \dots, g_m)$, where $h$ is symmetric and each $g_i$ is computed by a read-once formula with symmetric gates, of depth at most $d$. Let every $g_i$ be a function on $n_i$ variables with $a_i = s_0(g_i)$ and $b_i = s_1(g_i)$. By the inductive hypothesis, we know that $a_i b_i \ge n_i$. Since $n = \sum_{i=1}^m n_i$, we have that, $\sum_{i=1}^m a_i b_i \ge n$. Without loss of generality, we may assume that $a_1 \ge a_2 \ge \dots \ge a_m$ and $b_{\pi(1)} \ge b_{\pi(2)} \ge \dots \ge b_{\pi(m)}$ for a suitable permutation $\pi$ of $[m]$. Let $A_j := \sum_{i=1}^j a_i$ and $B_j := \sum_{i=1}^j b_{\pi(i)}$. Let $t := \tau(h)$ so $h(x) = z$ for all $x$ with $|x|_1 = t - 1$ and $h(y) = 1 - z$ for all $y$ with $|y|_1 = t$.

Since the formula is read-once, the $g_i$ depend on disjoint sets of variables, and so it is easy to see that for all $S$ with $|S| = t - 1$, we can find an assignment $\sigma$ to all the variables of $f$ such that (i) $g_i(\sigma_i) = 1$ for exactly those $i \in S$ and (ii) for $i \notin S$, $g_i(\sigma_i) = 0$ and $g_i$ has $a_i = s_0(g_i, \sigma_i)$ sensitive inputs.

It follows that $s_z(f) \ge \max_{\substack{S \subseteq [n] \\ |S| = m - t + 1}} \{\sum_{i \in S} a_i\} = A_{m-t+1}$.

Similarly, $s_{1-z}(f) \ge \max_{\substack{S \subseteq [n] \\ |S| = t}} \{\sum_{i \in S} b_i\} = B_t$.

$$ \text{So, } s_0(f)s_1(f) \ge A_{m-t+1}B_t = (a_1 + \dots + a_{m-t+1})(b_{\pi(1)} + \dots + b_{\pi(t)}). $$

Our proof is completed by the following claim whose proof is given in the full version.

**Claim 14.** For any $t$, $1 \le t \le m$, $A_{m-t+1}B_t \ge \sum_{i=1}^m a_i b_i$.

We therefore conclude that $s_0(f)s_1(f) \ge A_{m-t+1}B_t \ge \sum_{i=1}^m a_i b_i \ge n$.

<figure><img src="image_4.png" /></figure>
16:6 Sensitivity Conjecture for Read-k Formulas

► **Corollary 15.** Let $f$ be a Boolean function computed by a read once formula $C$ with symmetric gates. Then, $s(f) \ge \sqrt{n} \ge \sqrt{bs(f)}$.

Furthermore, this bound is tight whenever $n$ is a perfect square. To see the tightness of the bound, consider an OR of fan-in $\sqrt{n}$ over $\sqrt{n}$ disjoint AND's on $\sqrt{n}$ variables each. It is easy to see that both 0-sensitivity and 1-sensitivity of this function are exactly $\sqrt{n}$.

4 Read-k formulas

In the following, we will only consider AND-OR formulas (with positive and negative literals). In this section, we prove the sensitivity conjecture for read-k formulas with certain restrictions.

► **Theorem 16.** Let $f$ be computed by a regular read-k formula of depth $d$ with constants $k$ and $d$ such that any internal gate computes a non-constant function. Then, $s(f) = \Omega_{k,d}(\sqrt{bs(f)})$, where the hidden constant is a (rapidly decreasing) function of $k$ and $d$.

We prove this theorem in two stages:

- In Section 4.1, we first prove a lower bound for $s(f)$ in terms of $bs(f)$ when $f$ is computed by a read-k regular formula with large bottom fanin.

- Then, in Section 4.2, we remove the condition on the bottom fanin by defining a normal form for formulas and then reducing a formula with small bottom fanin to one in the normal form where the previous step applies.

**Notation:** When $C$ is an $(a_1, \dots, a_d)$-regular formula with AND-OR gates we will use $A(C, j)$ to denote the product,

$$A(C, j) = \prod_{\substack{l \in [j] \\ l \text{ is a } \wedge\text{-gates level}}} a_l.$$

As most of the times, the function $A$ will be used on the parameters $C$ and $j = d - 2$, we will denote $A(C, d - 2)$ by $A$.

4.1 Large bottom fan-in

In this section, we give a lower bound for sensitivity in terms of block sensitivity for read-k regular formulas with large bottom fanin.

4.1.1 1-Sensitivity when bottom gates are AND gates

We will first prove a lower bound on the 1-sensitivity of such formulas. We will show that given a formula $C$ it is possible to get an equivalent formula $C'$ which has certain nice properties. Specifically, all inputs on which $C'$ evaluates to 1 have large Hamming weight, which directly implies that the 1-sensitivity for this function is large.

► **Definition 17.** A parse tree $P$ of a formula $C$ computing $f$ is a subcircuit which is recursively defined as follows:

- The output gate of $C$ is in $P$.

- If an $\wedge$-gate belongs to $P$ then all its children are also in $P$.

- If an $\vee$-gate belongs to $P$ then exactly one of its children is in $P$.
It is easy to see that $f$ evaluates to 1 on an input $x$ if and only if $C$ contains a parse tree all of whose gates evaluate to 1. A simple induction also shows that every parse tree of a regular formula has $A(C, d-1)$ bottom gates.

**Definition 18.** The parse-read of $C$ is the maximum number of times any variable appears in any parse tree.

We will now consider two models. The first model is a (natural) restriction of our model of regular formulas: a variable can appear at most once under the same bottom gate. The second model is the general one without this restriction.

**Lemma 19.** Let $(a_1, \dots, a_d) \in (\mathbb{N} \setminus \{0\})^d$ with $a_d \ge 2 \log 4k$. Let $f$ be a non-constant function computed by an $(a_1, \dots, a_d)$-regular read-k and parse-read p formula such that the bottom gates are $\wedge$-gates and such that each variable appears at most once under any bottom gate. Then

$$s_1(f) \ge \left( \frac{a_d - 2 \log 4k + 1}{2p \log 4k} \right) A.$$

**Proof.** By regularity, any bottom gate of $C$ is the parent of $a_d$ literals. Let us group these literals into groups of size $\alpha$ whose value will be chosen later. The last group will be of size $a_d$ modulo $\alpha$. So we get $\lfloor a_d/\alpha \rfloor$ groups of $\alpha$ literals under every bottom gate. We want to modify $C$ to $C'$ such that each group contains at least one positive literal.

Let us randomly negate each variable. Each variable is independently chosen as positive or negative with probability $1/2$. Let $A_i$ be the event that the $i$th group has no positive literals (where the $i$th group is taken over all groups under all bottom gates). So $\Pr[A_i] = \frac{1}{2^\alpha}$. Every event $A_i$ is dependent on at most $k\alpha$ other $A_j$'s. Using the symmetric version of the Lovász Local Lemma we get that, if $e(k\alpha + 1) \le 2^\alpha$ then $\Pr[\bigcap A_i] > 0$.

Notice that $\alpha = \lfloor 2 \log(4k) \rfloor$ satisfies the previous inequality for all positive integers $k$. So there exists a new formula $C'$ such that every group will have at least one positive literal. Let $g$ be the function computed by $C'$. Note that we now have a fixed $\sigma$ such that for all $x$, $f(x \oplus \sigma) = g(x)$.

On any input $x \in g^{-1}(1)$ we get at least one parse tree in $C'$ all of whose gates evaluate to 1. Consequently, on any input $x$ in $g^{-1}(1)$, there are at least $A$ bottom $\wedge$-gates of $C'$ which evaluate to 1. As each variable can appear at most $p$ times in any parse tree, we have that $\forall x \in g^{-1}(1), |x|_1 \ge \left\lfloor \frac{A}{p} \left\lfloor \frac{a_d}{\alpha} \right\rfloor \right\rfloor \ge \frac{A(a_d - 2 \log 4k + 1)}{2p \log 4k}$.

Taking the input $x \in g^{-1}(1)$ with least Hamming weight we get that,

$$s_1(f, x \oplus \sigma) = s_1(g, x) \ge |x|_1 \ge \left( \frac{a_d - 2 \log 4k + 1}{2p \log 4k} \right) A.$$

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

It is interesting to notice that the proof can be turned into an algorithm for finding an input which has high sensitivity given any 1-input $x$. Namely, one just have to run the algorithmic version of Lovász Local Lemma to get the above bijection $\oplus\sigma$. Then find (by flipping the 1's from $x$) a locally minimal weight (under $\oplus\sigma$) assignment that still gives the output 1.

We will now remove the condition that every variable can occur at most once under any bottom gate. In doing so we will lose a factor of $k$ in the lower bound while also demanding a stronger constraint on the bottom fanin. This time around we use the general version of the Lovász Local Lemma to transform $C$ to $C'$. The rest of the proof then follows along similar lines to the proof of Lemma 19. The proof can be found in the full version.
16:8 Sensitivity Conjecture for Read-k Formulas

**Lemma 20.** Let $(a_1, \dots, a_d) \in (\mathbb{N} \setminus \{0\})^d$ with $a_d \ge k \log(3k)$. Let $f$ be a non-constant function computed by an $(a_1, \dots, a_d)$-regular read-k and parse-read p formula such that the bottom gates are $\wedge$-gates. Then

$$s_1(f) \ge \left( \frac{a_d - k \log(3k) + 1}{k p \log(3k)} \right) A.$$

4.1.2 The Sensitivity Conjecture for large bottom fan-in case

We will now combine previously known results with the statements proved in the section above to obtain some relations between sensitivity and block sensitivity.

The next lemma will help us relate the bound obtained for $s_1(f)$ to $C_1(f)$ of read-k regular formulas. The proof follows by induction and can be found in the full version.

**Lemma 21.** Let $f$ be a Boolean function computed by an $(a_1, \dots, a_d)$-regular formula $C$. Then, $C_1(f) \le A(C, d)$.

**Theorem 22.** Let $f$ be a non-constant Boolean formula computed by an $(a_1, \dots, a_d)$-regular read-k formula with parse-read p such that its bottom fanin $a_d$ is larger or equal to $(3 \log 4k)$ and such that any variable appears at most one time under each bottom gate. Then

$$s(f) \ge \sqrt{\frac{\mathrm{bs}(f)}{10p \log 4k}}.$$

Moreover, when a variable can occur multiple times under each bottom gate and the bottom fan-in $a_d \ge 2k \log 3k$, we have

$$s(f) \ge \sqrt{\frac{3bs(f)}{10kp \log 3k}}.$$

**Proof.** Let us start by the first point of the theorem. By considering $f$ or $\neg f$, we can assume that the bottom layer is composed of $\wedge$-gates. By Lemma 19, we have that,

$$s_1(f) \ge \left( \frac{a_d - 2 \log 4k + 1}{2p \log 4k} \right) A.$$

From Lemma 21 we have $C_1(f) \le a_d A$. Since $a_d \ge 3 \log 4k$, $a_d - 2 \log 4k \ge a_d/3$,

$$s_1(f) \ge \frac{3A + C_1(f)}{6p \log 4k} \ge \frac{C_1(f) + 1/2}{6p \log 4k}.$$

Using Lemma 8 we get, $s(f) \ge s_1(f) \ge \frac{bs_1(f)}{6p \log 4k}$. We also get by Theorem 9,

$$s(f)^2 \ge s_1(f) \cdot s_0(f) \ge \frac{bs_0(f)}{4p \log 4k}.$$

$$\text{Since } \mathrm{bs}(f) = \max(\mathrm{bs}_1(f), \mathrm{bs}_0(f)), \text{ } 5s^2 \ge 2s^2 + 3s \ge \frac{\mathrm{bs}_0(f)}{2p \log 4k} + \frac{\mathrm{bs}_1(f)}{2p \log 4k} \ge \frac{\mathrm{bs}(f)}{2p \log 4k}.$$

Consequently, $s \ge \sqrt{\frac{\mathrm{bs}(f)}{10p \log 4k}}$, proving the first part. The second part of the theorem follows analogously using Lemma 20. $\quad$

The following corollary follows from the lower bound for sensitivity proved in [19]. A detailed proof can be found in the full version of the paper.

**Corollary 23.** Let $f$ be a non-constant Boolean formula computed by an $(a_1, \dots, a_d)$-regular read-(log n) formula with bottom fan-in at least $\log^2 n$. Then $s(f) \ge \tilde{\Omega}(\mathrm{bs}(f)^{1/4})$ where the $\tilde{\Omega}$ notation hides some logarithmic terms.
## 4.2 Removing the condition on the bottom fan-in

In this section, we complete the proof of Theorem 16. We note that when the depth is constant but the size of the formula is large enough, there has to be a level at which the fanin is sufficiently large. If one of the last two fanins is large, we can apply an argument quite similar to the one in the previous section. Otherwise, we can switch these two layers while incurring a significant blow-up (but still only as a function of depth and read-multiplicity) in certain circuit parameters, while reducing the depth of the circuit. We continue switching the last two layers until one of their fanins is sufficiently large, which is ensured because the circuit is of constant depth.

### 4.2.1 Normal form by switching:

For notational convenience, we number the layers of a depth-d circuit as $L_1, \dots, L_d$ with $L_1$ being just the root (output) gate and $L_d$ the bottom layer (with inputs feeding into them) of gates. Also, we define the following function over $\mathbb{N}$ for later reference:

$$H(x) := 24 \cdot (3x)^{2x} x^4 \log 3x. \qquad (1)$$

As mentioned above, we will transform our formula into an equivalent formula where the fanin in the last or the last but one layer is sufficiently large. Such a representation for Boolean functions will be called a normal form:

**Definition 24.** A formula is in $(k; a_1, \dots, a_d)$-normal form if the following properties hold:

1. the formula is alternating and $(a_1, \dots, a_d)$-regular, i.e., fanin of all gates in $L_i$ is $a_i$,

2. the formula is read-$k$,

3. the bottom layer $L_d$ is composed of $\wedge$-gates,

4. at least one of the two following conditions on the fanins of the two bottom layers $L_{d-1}$ and $L_d$ is true:

- $a_d \ge 2k \log 3k$,

- under each $\vee$-gate in $L_{d-1}$, i.e., one layer above the bottom layer, there are at least $H(k)$ non-constant $\wedge$-bottom gates.

As we will switch adjacent layers of the formula, let us start by bounding the increase we get by such a procedure. Let the size and width of a DNF (respectively CNF) be the fanin of its first layer and second layer respectively.

**Lemma 25.** If $f$ is a function computed by a read-$k$ regular DNF (respectively CNF) of size (top fanin) $a$ and width $b$, then it is also computed by a read-(kb$^{(a-1)}$) CNF (respectively DNF) of size $b^a$ and width $a$.

Now we will focus on the last two layers we get after some number of switches in the formula. We will recursively define certain functions $T_i$ below. Intuitively, $T_1$ is the fanin of the bottom layer without any switches and $T_{i+2}$ is the fanin of the layer just above the bottom layer after $i$ switching steps. Note that a depth $d$ circuit becomes a depth $d-i$ circuit after $i$ switches and merges of adjacent layers (after switching) of gates of the same type. Thus $T_{i+2}$ is the fanin of layer $L_{d-i-1}$ in the transformed circuit after $i$ applications of switching and merging.

Formally, the family of functions $T_i: \mathbb{N}^i \to \mathbb{N}$, where $i$ is a positive integer, is defined as

$$\left\{ \begin{array}{l} T_0 = 1 \\ T_1(a) = a \\ T_p(a_1, \dots, a_p) = a_1 \cdot (T_{p-2}(a_3, \dots, a_p))^{T_{p-1}(a_2, \dots, a_p)} \quad \text{if } p \ge 2. \end{array} \right.$$
16:10 Sensitivity Conjecture for Read-k Formulas

In what follows, the function $T_i$ will almost always be evaluated on the fanins of the last $i$ layers of the formula. So, we will sometimes use the shorter notation $T_i(\mathbf{a})$ to designate $T_i(a_{d-i+1}, \dots, a_d)$.

Observe that most of the non-regular formulas can be converted into a regular one by inserting gates or subtrees of gates that compute identically constant functions. Since we want to avoid this, we will define *purely regular formulas* as regular formulas in which each internal gate computes a non-constant Boolean function.

In the next claim, we compute the parameters of our new formula after several switches. The proof of the claim is by induction on the number of switchings $i$ and the details can be found in the full version of the paper.

**Claim 26.** Suppose $f$ is computed by a purely $(a_1, \dots, a_d)$-regular read-k formula. Then for all integers $i \in [0, d-2]$, $f$ is computable by an $(a_1, \dots, a_{d-i-2}, u, v)$-regular read-$(kuv / (\prod_{j=d-i-1}^d a_j))$ formula where

$$u = T_{i+2}(a_{d-i-1}, \dots, a_d) \quad \text{and} \quad v = T_{i+1}(a_{d-i}, \dots, a_d)$$

such that under any gate in layer $L_{d-i-1}$, i.e., one layer above the bottom layer of gates, there are at least $a_{d-i-1}$ non-constant bottom gates.

Recall the function $H(x)$ from (1). We inductively define $R_i(k)$ as

$$\begin{cases} R_0(k) = R_1(k) = k \\ R_p(k) = k \prod_{j=1}^{p-1} T_j(H(R_{j-1}(k)), \dots, H(R_0(k)))^{T_{j+1}(H(R_j(k)), \dots, H(R_0(k))) - 1} \text{ if } p \ge 2. \end{cases}$$

Intuitively, the $R_i(k)$'s bound the read value of the formula after $i-1$ switches of the bottom layers. As the functions $R_p$ will always be used on the parameter $k$ (the read value of the original formula), we will usually denote $R_p(k)$ by the simpler notation $R_p$.

We are now ready to prove that we can transform a sufficiently large regular formula into a formula in normal form. Proof of the following lemma appears in the full version.

**Lemma 27.** If $f$ is computed by a purely $(a_1, \dots, a_d)$-regular read-k formula with size larger than $H(R_d)$ then there exists $i \in [0, d-2]$ such that either $f$ or $\neg f$ can be computed by a formula in $(R_{i+1}; a_1, \dots, a_{d-i-2}, u, v)$-normal form with

$$u = T_{i+2}(a_{d-i-1}, \dots, a_d) \quad \text{and} \quad v = T_{i+1}(a_{d-i}, \dots, a_d).$$

Moreover,

- the index $i$ is such that for any $p \ge d-i$ we have $a_p \le H(R_{d-p})$, and

- under each gate in one layer above the bottom one, i.e., $L_{d-i-1}$, there are at least $a_{d-i-1}$ non-constant gates, where $a_{d-i-1} \ge H(R_{i+1})$.

Now since our new formula's last or last but one fanin is sufficiently large, we can prove a lower bound on the sensitivity as was done in Theorem 22. The sketch of the proof is similar to the one of Theorem 22, but the fact that we now consider the last two layers (instead of the last layer only) makes details a bit more complicated.

**Theorem 28.** If $f$ is computed by a purely $(a_1, \dots, a_d)$-regular read-k formula with size larger than $H(R_d(k))$, then

$$s(f) \ge \sqrt{\frac{3bs(f)}{5R_{d-1}(k)H(R_{d-1}(k))^{(d+1)/2}}} = \Omega_{k,d}(\sqrt{bs(f)}).$$
Since the function $R_{d-1}(k)$ only depends on $d$ and $k$, Theorem 16 immediately follows. One can notice that the hidden constant in this theorem is approximatively the inverse of the tetration $2^{d-2}k = \underbrace{k^{k^{\cdot^{k}}}}_{2d-2}$.

**Proof of Theorem 28.** By Lemma 27, we know that $f$ (or $\neg f$) can be computed by a $(k', a_1, \dots, a_{d'-2}, u, v)$-regular formula in normal form where $k' = R_{d-d'+1}(k)$. Here $d'$ is the depth of the new (equivalent) formula after applying $d-d'$ switches and merges. If the bottom fanin is larger than $2k' \log(3k')$ (the first condition for the fanins in the normal form) then using Theorem 22 we get that,

$$s(f) \ge \frac{1}{k'} \sqrt{\frac{3bs(f)}{10 \log 3k'}} \ge \sqrt{\frac{3bs(f)}{5R_{d-1}(k)H(R_{d-1}(k))^{(d+1)/2}}}$$

Otherwise we have that under each gate in $L_{d'-1}$, there are at least $a_{d'-1} \ge H(R_{d-d'+1})$ non-constant bottom gates.

In this case, we want to give a similar argument as in proof of Lemma 19 for the last but one layer instead of the last layer. Hence, we would like to have $\wedge$-gates at the last but one layer. So we will consider ($\neg f$) if necessary. By Lemma 27, such a bottom $\wedge$-gate of $C$ is the parent of at least $a_{d'-1}$ non-constant bottom $\vee$-gates. Let us group these non-constant $\vee$-gates into groups of size $\alpha = \lfloor H(k')/2 \rfloor$. We now get $C'$ from $C$ so that each group contains at least one $\vee$-gate which has only positive literals under it. Let $g$ be the function computed by $C'$.

Using a similar argument as in proof of Lemma 19 (proved in the full version),

**Claim 29.** For all $x$ in $g^{-1}(1)$

$$|x|_1 \ge \left\lfloor \frac{A'}{k'} \left\lfloor \frac{a_{d'-1}}{\alpha} \right\rfloor \right\rfloor \ge \frac{A'(2a_{d'-1} - H(k') + 1)}{k'H(k')} \quad \text{with } A' = A(C, d' - 2).$$

Taking the input $x \in g^{-1}(1)$ with least Hamming weight we get that,

$$s_1(g, x) \ge |x|_1 \ge \frac{A'(2a_{d'-1} - H(k') + 1)}{k'H(k')} \ge \frac{A'a_{d'-1} + 1}{k'H(k')} \ge \frac{A(C, d) + 1}{k'H(k')H(R_{d-3})^{(d-d'+1)/2}}$$

since for any $p \ge d' + 1$ we have that $a_p \le H(R_{d-p}) \le H(R_{d-3})$ and we only need to consider alternate layers in the definitions of $A$ and $A'$.

Since the circuit is in normal form we know that $k' \le R_{d-d'+1}(k) \le R_{d-1}(k)$. Using a proof similar to Lemma 19 we get that, $s(f) \ge \sqrt{\frac{3bs(f)}{5R_{d-1}(k)H(R_{d-1}(k))^{(d+1)/2}}}$. ▶

# 5 Sensitivity Lower Bounds for DNFs

In this section, we get sensitivity lower bounds for functions computed by read-restricted DNFs. A DNF is said to be *minimal* if no proper sub-formula of such a DNF computes the same function.

**Notation:** For a DNF $C$ let $a_1$ denote its top fanin and $a_{21}, \dots, a_{2a_1}$ its bottom fanins, with $a_2 = a_{21} \ge a_{22} \ge \dots \ge a_{2a_1}$.
## 5.1 Regular read-k DNFs of large width

We can adapt Corollary 23 in the case where the DNF in question is regular and its width is sufficiently large:

**Corollary 30.** Let $f$ be a Boolean function computed by a minimal regular DNF of size $n^c$, for some $c > 0$ with width larger than or equal to $6 + 3c \log n$. Then, $s(f) \ge \frac{bs(f)^{1/3}}{2\sqrt{5 \max(2, c)}}$.

## 5.2 Read-k DNFs of small size

In this section we will remove the constraints of regularity and large width for DNFs, thus proving the sensitivity conjecture for all functions computed by read-k DNFs.

The first lemma ensures a lower bound on $s_0(f)$ for functions computed by read-k DNFs. The proof can be found in the full version.

**Lemma 31.** Let $f$ be a Boolean formula computed by a minimal read-k DNF $C$. Then $s_0(f) \ge \frac{a_1}{ka_2}$.

The second lemma states that the sensitivity of a read-k DNF is lower bounded by a function of its maximum bottom fanin.

**Lemma 32.** Let $f$ be a Boolean function computed by a minimal read-k DNF $C$. Then $s_1(f) + (1+k)s_0(f) \ge a_2$.

**Proof.** Let the bottom $\wedge$-gates be $W_1, \dots, W_{a_1}$ with fanins $a_2 = a_{21} \ge \dots \ge a_{2a_1}$ respectively. Let the variables under $W_i$ be $x_{i1}, \dots, x_{ia_{2i}}$.

Let us define two sets:

- $z \in P_1$ if and only if $W_1(z) = 1$ and for all $j > 1$, $W_j(z) = 0$,

- $y \in P_2$ if and only if $W_1(y) = 1$ and $y$ is sensitive on the variable $x_{11}$.

By minimality of $C$, we can find an input

- $z_0$ in $P_1$, otherwise removing the gate $W_1$ would not modify the function,

- $y_0$ in $P_2$, otherwise we can remove the leaf corresponding to $x_{11}$ from $W_1$.

In fact it would be great to find an input which belongs to both $P_1$ and $P_2$, but unfortunately, it is not always possible. However, we show we can find such a pair $(z, y)$ such that the Hamming distance between them is small. The next two claims are proved in the full version.

**Claim 33.** There exists a pair of inputs $(z_1, y_1) \in P_1 \times P_2$ such that the Hamming distance between $z_1$ and $y_1$ is at most $s_0(f) - 1$.

Let $J \subseteq [2, a_2]$ be the variables which appear under $W_1$ and which are sensitive on $z_1$, so $s_1(f) \ge |J|$. Let $\bar{J} = [2, a_2] \setminus J$. Hence, it is sufficient to show:

**Claim 34.** $s_0 \ge |\bar{J}| - ks_0 + 1$.

**Theorem 35.** Let $f$ be a Boolean formula computed by a read-k DNF. Then $(k+2)s(f) \ge n^{1/3}$. In particular, if $k \le n^{1/3-\epsilon} - 2$, we get $s(f) \ge n^\epsilon \ge bs(f)^\epsilon$.

**Proof.** Using Lemma 32 we get that, $(k+2)s(f) \ge s_1(f) + (1+k)s_0(f) \ge a_2$. By Lemma 31 we know that, $s_0(f) \ge \frac{a_1}{ka_2} \ge \frac{n}{ka_2^2}$. Combining these two inequalities we get,

$$s^3(f) \ge \left( \frac{a_2}{k+2} \right)^2 \frac{n}{ka_2^2} \ge \frac{n}{k(k+2)^2}$$

and so $(k+2)s(f) \ge n^{1/3}$. In particular, when $k+2 \le n^{1/3-\epsilon}$, we get $s(f) \ge n^\epsilon \ge bs(f)^\epsilon$. ◀
References

1 Scott Aaronson. The "sensitivity" of 2-colorings of the $d$-dimensional integer lattice. blog-post, July 2010. URL: http://mathoverflow.net/questions/31482/.

2 Noga Alon and Joel H Spencer. *The Probabilistic Method*. John Wiley and Sons, 1994.

3 Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In *International Colloquium on Automata, Languages and Programming (ICALP) 2014, Part I*, pages 101–113, 2014. doi:10.1007/978-3-662-43948-7_9.

4 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.

5 Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. In *39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA*, pages 352–361, 1998. doi:10.1109/SFCS.1998.743485.

6 Meena Boppana. Lattice variant of the sensitivity conjecture. *Electronic Colloquium on Computational Complexity (ECCC)*, 19:89, 2012.

7 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.

8 Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. In *Conference on Computational Complexity (CCC)*, pages 163–167, 2005.

9 Stephen 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.

10 Justin Gilmer, Michal Koucký, and Michael E. Saks. A new approach to the sensitivity conjecture. In *Innovations in Theoretical Computer Science, ITCS*, pages 247–254, 2015.

11 Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions. to appear *CCC 2016*, 2016.

12 Craig Gotsman and Nathan Linial. The equivalence of two problems on the cube. *Journal of Combinatorial Theory, Series A*, 61(1):142–146, 1992.

13 Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. *Theory of Computing, Graduate Surveys*, 4:1–27, 2011.

14 Claire Kenyon and Samuel Kutin. Sensitivity, block sensitivity, and 1-block sensitivity of Boolean functions. *Information and Computation*, 189(1):43–53, 2004.

15 Hiroki Morizumi. Sensitivity, block sensitivity, and certificate complexity of unate functions and read-once functions. *IFIP TCS*, 2014.

16 Noam Nisan. CREW PRAMs and decision trees. In *Symposium on Theory of Computing*, pages 327–335, 1989.

17 Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomial. In *Symposium on Theory of Computing*, pages 462–467, 1992.

18 David Rubinstein. Sensitivity vs. block sensitivity of boolean functions. *Combinatorica*, 15(2):297–299, 1995.

19 Hans-Ulrich Simon. A tight $\Omega(\log \log n)$-bound on the time for parallel RAM's to compute nondegenerated Boolean functions. *Foundations of Computation Theory, Lecture Notes in Computer Science*, 158(1):439–444, 1983.

20 Xiaoming Sun. Block sensitivity of weakly symmetric functions. *Theor. Comput. Sci.*, 384(1):87–91, 2007.

21 Avishay Tal. On the sensitivity conjecture. In *International Colloquium on Automata, Languages and Programming (ICALP)*, 2016.
16:14 Sensitivity Conjecture for Read-k Formulas

22 György Turán. The critical complexity of graph properties. *Inf. Process. Lett.*, 18(3):151–153, 1984.