On the Complexity of Hazard-Free Formulas

[11, 13] obtained exponential lower bounds on the hazard-free computation of many Boolean functions using Theorem 12. However, there are Boolean functions for which the hazard-derivative method fails to provide optimal lower bounds on hazard-free complexity due to the low monotone complexity of the hazard-derivatives. [12] highlights this issue and refers to it as the monotone barrier. They define breaking the monotone barrier as achieving stronger lower bounds than those obtained by the hazard-derivative method.

As an example of a result that breaks the monotone barrier, [12] note that the hazard-derivatives of the parity function on $n$ variables, ${\text{XOR}}_n$, are simply OR functions on $n$ literals, which have trivial formulas of size $n$. On the other hand, it is known that the De Morgan formula complexity of ${\text{XOR}}_n$ is $\mathrm{\Omega }(n^2)$, while it is not hard to see that any formula for ${\text{XOR}}_n$ is hazard-free.

To quantify the gap between the hazard-free complexity of a given Boolean function and the monotone complexity of its hazard-derivatives, we define a measure, similar to the one defined in [13, Section $7$], which we refer to as the monotone gap.

For example, the monotone gap of ${\text{XOR}}_n$ is $\mathrm{\Omega }(n)$. In an attempt to understand the power of the hazard-derivative method (or its weaknesses), we wish to answer the following:

[12] studied a generalization of the classic Karchmer-Wigderson game [15] in the hazard-free setting.

As ${\text{KW}}_f^{𝔲}\subseteq {\tilde{f}}^{-1}(1)\times {\tilde{f}}^{-1}(0)\times [n]$, and every $x\in {\tilde{f}}^{-1}(1)$ and $y\in {\tilde{f}}^{-1}(0)$ are valid inputs⁴⁴4There must exist a coordinate $i\in [n]$ such that $x_i\ne y_i$ and $x_i,y_i$ are stable. Otherwise, $x,y$ have a common resolution, in contradiction to Definition 8., ${\text{KW}}_f^{𝔲}$ has a potentially larger set of inputs than the classic game. As a result, the communication matrix may be more complex. Similarly to the classic KW game, the hazard-free KW game preserves a tight connection between the underlying communication problem complexity and the optimal hazard-free formula depth and size.

Like the monotone version of the KW game, [12] proved that the communication complexity of ${\text{KW}}_f^{𝔲}$ does not decrease even if it is played only on the prime implicants of $f$ and the prime implicates of $f$.

The notion of prime implicants and prime implicates is well established in Boolean algebra. Following [12], we provide analogous definitions using ternary algebra as previously defined in [17][p.3] and [12][p.7].

For the remainder of the paper, we abuse notation and use ${\text{KW}}_f^{𝔲}$ to denote the restricted game. We next define the communication matrix of the ${\text{KW}}_f^{𝔲}$ game.

Another interesting observation is that, for a monotone function, the hazard-free KW game captures the monotone formula complexity.

Consequently, the size and depth of an optimal hazard-free formula are identical to those of its monotone counterpart. This provides a proof of Theorem 9 for formulas instead of circuits.

By using communication complexity methods to prove lower bounds on hazard-free formulas, [12, Theorems 19, 23] determined the exact hazard-free formula size of the multiplexer function.

This result is much better than what can be achieved using the hazard-derivative method since the hazard-derivatives of the multiplexer function have quasi-linear monotone formula complexity (see [12, Proposition 1]).

An immediate consequence of Theorem 24 is that any Boolean function $f$ can be implemented by a hazard-free formula of size $2\cdot 3^n-1$. Indeed, it holds that:

therefore, the hazard-free formula for the multiplexer, when hardwired the truth table of $f$, gives a hazard-free formula for $f$. This result is the first to break the $O(\sqrt{n}\cdot 3^n)$ upper bound of Huffman [10].

We note that this state of knowledge is much poorer compared to what is known for hazard-free circuits. Analogous to [28, 23], Jukna [13, Section 7] proved that any Boolean function has a hazard-free circuit of size $O(2^n/n)$, applying the following:

Therefore, naturally, we can construct a hazard-free circuit for $f:{\{0,1\}}^n\to \{0,1\}$ by using hazard-free implementations $C_0$ and $C_1$ for $f_0(x_1,\mathrm{\dots },x_{n-1}):=f(x_1,\mathrm{\dots },x_{n-1},0)$ and $f_1(x_1,\mathrm{\dots },x_{n-1}):=f(x_1,\mathrm{\dots },x_{n-1},1)$, respectively. However, in the case of formulas, the size of the formula obtained by (1) is $O(3^n)$, since it is composed of 3 hazard-free formulas over $n-1$ bits.⁵⁵5Note that the extra $(C_0\wedge C_1)$ term is necessary. Say that for some $x\in {\{0,𝔲,1\}}^{n-1}$ we have $\tilde{f}(x,𝔲)=1$. Hence, by definition, we also have ${\tilde{f}}_0(x)=1,{\tilde{f}}_1(x)=1$, and so $C_0(x)=1,C_1(x)=1$. But, $(\neg x_n\wedge C_0)\vee (x_n\wedge C_1)$ will evaluate to $𝔲$.

This result matches the lower bound obtained via the same counting arguments used in the Boolean setting. In particular, for a typical Boolean function (i.e., one sampled uniformly at random from all Boolean functions on $n$ bits), we have ${\text{size}}_C^{𝔲}(f)=\mathrm{\Theta }({\text{size}}_C(f))$.

On the other hand, counting arguments give a lower bound of order $\mathrm{\Omega }(2^n/\log n)$ for the size of the hazard-free formula of a random Boolean function [27, 28], whereas Theorem 24 only implies an $O(3^n)$ upper bound. Thus, there is an exponential gap between the two bounds. This naturally leads to the following question.

Karchmer, Raz and Wigderson [14] introduced the KRW conjecture as an approach for establishing super-polynomial lower bounds for De Morgan formulas. Proving this conjecture would imply $\text{P}⊈{\text{NC}}^1$. A detailed discussion can be found in [21].

To state the conjecture, we define the block-composition of two Boolean functions $f:{\{0,1\}}^n\to \{0,1\}$ and $g:{\{0,1\}}^m\to \{0,1\}$ as

where $X$ is a $n\times m$ Boolean matrix, and $X_i\in {\{0,1\}}^m$ is the $i$’th row of $X$. For a Boolean function $f$, we denote with $0p{t}_F(f)$ the depth of the shallowest formula computing $f$.

Roughly, the conjecture states that the smallest depth formula for computing $f\diamond g$ is obtained from the composition of the shallowest formula for $f$ and the shallowest formula for $g$. We next state an analogous conjecture in the hazard-free setting.

Similarly to [4, 26], we state a stronger version of the conjecture on the formula size.

The KRW conjecture has been extensively studied through various special cases and simplified communication problems, as intermediate steps toward proving Conjecture 27. The monotone version of the KRW conjecture is most related to the hazard-free setting due to the connection to the hazard-derivative, which is a monotone function.

In [26, Theorem 3.1], Conjecture 30 was proved for monotone inner functions $g$ whose depth complexity can be lower-bounded by a lifting theorem. In an earlier work, [14] observed that the monotone KW game can be played on the prime implicants and implicates of the monotone function, aligning well with the results concerning the hazard-free KW game presented in Theorem 22. Notably, the hazard-free KRW conjecture generalizes the monotone KRW conjecture, as proving the former for every $f$ and $g$ would also imply the latter.

Let us discuss the underlying intuition. The hazard-derivative is a monotone function and so its prime implicants and prime implicates are more structured, namely, $P_1^{(\mathrm{d}f(x;\cdot ))}\subseteq {\{1,𝔲\}}^n$ and $P_0^{(\mathrm{d}f(x;\cdot ))}\subseteq {\{0,𝔲\}}^n$. Therefore, it is enough to consider the maximal and the minimal resolutions with respect to $\le$:

Consider $q_0\in P_0^{(\mathrm{d}f(x;\cdot ))}$. The $1$s in $\widehat{q_0}$ represent all the coordinates in $x$ that can be perturbed while the output $\tilde{f}(x+𝔲\widehat{q_0})$ still equals $f(x)=b$. Since $q_0$ is prime, it should not be possible to add more $𝔲$s to it, and consequently to $x+𝔲\widehat{q_0}$. This is the same as saying that $x+𝔲\widehat{q_0}=p_b\in {P_b^{(f)}|}_x$. Since $𝔲\widehat{q_0}=q_0$, it follows that $q_0=x+p_b$. The other direction is more intuitive: for $p_b\in {P_b^{(f)}|}_x$, the $0$’s in $x+p_b$ encode exactly the stable coordinates in $p_b$. This is a minimal subset of coordinates that must not be perturbed in $x$ if we wish to get the output $f(x)$.

Consider $q_1\in P_1^{(\mathrm{d}f(x;\cdot ))}$. The $1$s in $\check{q_1}$ represent all the coordinates in $x$ that must be perturbed in order for $\tilde{f}(x+𝔲\check{q_1})$ to be equal $𝔲$. Hence, there must be a resolution $z\in R(x+𝔲\check{q_1})$ for which $f(z)\ne f(x)$. We prove that for every $q_1\in P_1^{(\mathrm{d}f(x;\cdot ))}$ such $z$ is unique among $R(x+𝔲\check{q_1})$. Specifically, $z$ is the resolution that differs from $x$ in the the maximal number of coordinates possible, that is, in all coordinates for which $\check{q_1}$ equals $1$. Since $f(z)=\neg b$ there is some $p_{\neg b}\in P_{\neg b}^{(f)}$ such that $p_{\neg b}\stackrel{{}_{𝔲}}{\le }z$. We then show that $q_1={(p_{\neg b}+x)|}_{0\Leftarrow 𝔲}$, relying on the fact that $z$ is unique.

Note that unlike Lemma 39, we do not get a complete characterization of the prime implicants of the hazard-derivative. There may be $p_{\neg b}\in P_{\neg b}^{(f)}$ such that for $p:={(p_{\neg b}+x)|}_{0\Leftarrow 𝔲}$ there are multiple $z\in R(x+𝔲\check{p})$ such that $f(z)\ne f(x)$. For those, we prove that ${(p_{\neg b}+x)|}_{0\Leftarrow 𝔲}$ are implicants of $\mathrm{d}f(x;\cdot )$ (but not prime).

Let $M_{{\text{KW}}_f^{𝔲}}$ and $M_{{\text{KW}}_{\mathrm{d}f(x;\cdot )}^{𝔲}}$ represent the communication matrix of the hazard-free KW game of $f$ and $\mathrm{d}f(x;\cdot )$, respectively. Let $M_x$ be the submatrix of $M_{{\text{KW}}_f^{𝔲}}$ with labels ${P_{\neg b}^{(f)}\times P_b^{(f)}|}_x$. Our characterization of the prime implicants and prime implicates of $\mathrm{d}f(x;\cdot )$, allows us to prove the following, as illustrated in Figure 3(a):

Proposition 42 can be viewed as an alternative proof for Theorem 12 for formulas. We achieve Proposition 42 through the following observation:

In words, for every $q_1\in P_1^{(\mathrm{d}f(x;\cdot ))}$ and $q_0\in P_0^{(\mathrm{d}f(x;\cdot ))}$, which label a row and a column of $M_{{\text{KW}}_{\mathrm{d}f(x;\cdot )}^{𝔲}}$, we can choose $p_b\in {P_b^{(f)}|}_x$ and $p_{\neg b}\in P_{\neg b}^{(f)}$, which label a row and a column of $M_x$, that yield $q_1$ and $q_0$. Moreover, the correspondence preserves the set of stable and different coordinates between $(q_1,q_0)$ and $(p_b,p_{\neg b})$, hence the associated entries in $M_{{\text{KW}}_{\mathrm{d}f(x;\cdot )}^{𝔲}}$ and $M_x$ are identical.

A concrete example is shown in Figures 2(a) and 2(b), where the same colors as in Figure 3(a) are used for $M_{1100}$ and $M_{{\text{KW}}_{\mathrm{d}{f}_{\text{prime}}(1100;\cdot )}^{𝔲}}$. It can be verified that $𝔲1𝔲0\in P_0^{(f_{\text{prime}})}$ yields $𝔲0𝔲0\in P_0^{(\mathrm{d}{f}_{\text{prime}}(1100;\cdot ))}$ and $001𝔲\in P_1^{(f_{\text{prime}})}$ yields $111𝔲\in P_1^{(\mathrm{d}{f}_{\text{prime}}(1100;\cdot ))}$ with the corresponding entries both equal to $\{2\}$.

Next, we make the simple but important observation. Certain rows, which we refer to as “super-rows”, can be removed from a communication matrix without effecting its complexity. A super-row is a row $r$ in the matrix such that there exists another row $r^{\prime }$, called a sub-row, whose every entry is a subset of the matching entry in $r$.

It is not too difficult to see that the rows in $M_x$ that are associated with $p_{\neg b}\in P_{\neg b}^{(f)}$ such that ${(p_{\neg b}+x)|}_{0\Leftarrow 𝔲}\in I_1^{(\mathrm{d}f(x;\cdot ))}\setminus P_1^{(\mathrm{d}f(x;\cdot ))}$ are super-rows. Implicants that are not prime, by definition, contain “extra” stable bits that can be replaced with $𝔲$ while preserving the output of the function. Therefore, these rows contain possibly more valid answers to the ${\text{KW}}^{𝔲}$ on $\mathrm{d}f(x;\cdot )$ than the ones associated with $P_1^{(\mathrm{d}f(x;\cdot ))}$. Figures 2(a) and 2(b) demonstrate this claim, as the super rows in 2(a) correspond to $\{𝔲011,0𝔲11,01𝔲1\}$, which yielded $\{𝔲111,1𝔲11,1𝔲𝔲1\}$ in our previous calculation.

Following our observation, the super-rows can be removed without changing the complexity of $M_x$. Most importantly, removing them results in $M_{{\text{KW}}_{\mathrm{d}f(x;\cdot )}^{𝔲}}$. Hence, $M_x$ and $M_{{\text{KW}}_{\mathrm{d}f(x;\cdot )}^{𝔲}}$ are equivalent in terms of communication complexity. This highlights the importance of the hazard-derivative, which captures the communication complexity of $M_x$, which is a larger submatrix of $M_{{\text{KW}}^{𝔲}}$.