| Sbornik: Mathematics |
|
|
|
|
|
Half-duplex communication complexity with adversary can be less than the classical communication complexity N. K. Vereshchaginab , M. V. Dektiareva a Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia b Faculty of Computer Science, National Research University Higher School of Economics, Moscow, Russia
Bibliographic databases:
    § 1. IntroductionIn the classical model of communication complexity introduced by Yao in [11], we consider a cooperative game between two players, Alice and Bob, who want to compute $f(x,y)$ for a given function $f$. Alice knows only $x$ and Bob knows only $y$. To do this Alice and Bob can communicate by sending messages to each other, one bit per round. An important property of this communication model is as follows: in each round one player sends a bit message while the other player receives it. Algorithms in this model are called communication protocols. The depth of a protocol is defined as the number of bits it communicates in the worst case. The minimum possible depth of a protocol to compute $f$ is called the communication complexity of $f$. This model was generalized in [2] to a model describing communication over a so-called half-duplex channel. A well-known example of half-duplex communication is talking via walkie-talkie: one has to hold a ‘push-to-talk’ button to speak to another person, and one has to release it to listen. We consider a communication model where players are allowed to speak simultaneously. If two persons try to speak simultaneously, that is, both walkie-talkies are in the sending mode, then they do not hear each other and both messages are lost. We will consider communication models in which the players are allowed to send messages simultaneously, but in this case these messages get lost. The communication protocol over a half-duplex channel is also divided into rounds. To make such a division, we assume that the players have synchronized clocks. Every round each player chooses one of three actions: send 0, send 1, or receive. Thus we distinguish three types of rounds.
More specifically, the model described is called the communication model with adversary. In [2] two other models were also considered: the half-duplex model with silence (in a silent round both players receive a special symbol silence, and so they know that a silent round occurs) and the half-duplex model with zero (in a silent round both players receive 0). More specifically, the half-duplex complexity with adversary of a function is defined as the minimum number of rounds needed to compute the function on its domain, assuming that the adversary can choose any bits in silent rounds. One can show that the half-duplex communication complexity with adversary is sandwiched between the classical complexity and one half of it [2]. The original motivation to study these types of communication models arose from the question of the complexity of Karchmer–Wigderson games [3] for multiplexors. A detailed exposition of this motivation and recent results in this direction can be found in [4]–[7]. Here we just present a toy example in which half-duplex complexity arises quite naturally. Assume that for each parameter $a$ (ranging over a finite set) a function $f_a\colon X\times Y\to \{0,1\}$ is given. Our goal is to prove that for some $a$ the classical communication complexity of $f_a$ is larger that a certain number $d$. Assume also that we can prove the same lower bound $d$ for the classical communication complexity of the multiplexor game defined as follows: Alice obtains a pair $(x,a)$, Bob obtains a pair $(y,b)$, and they want to compute $f_a(x,y)$ if $a=b$. Otherwise, if $a\ne b$, then their protocol can return any result. It can seem that from this we can deduce the required lower bound for $f_a$ for some $a$. Indeed, by way of contradiction, assume that for every $a$ there is a classical depth $d$ communication protocol $\Pi_a$ that computes $f_a$. Then consider the following depth $d$ communication protocol for the multiplexor game: if Alice obtains a pair $(x,a)$ and Bob obtains a pair $(y,b)$, then Alice finds the lex-first depth $d$ protocol for $f_a$ and Bob the lex-first depth $d$ protocol for $f_b$. Then they run the protocols found. If $a=b$, then they run the same protocol, which outputs $f_a(x,y)$. Otherwise, if $a\ne b$, their protocols can output different results. This problem is easy to overcome: Alice sends her output to Bob, which costs only one extra bit of communication. However, there is a more complicated problem: the protocols $\Pi_a$ and $\Pi_b$ can simultaneously receive or send bits. Thus actually the protocol constructed is a half-duplex and not a classical communication protocol for multiplexor game. hence we need a lower bound $d$ for the half-duplex communication complexity of the multiplexor game! There are several examples of functions whose half-duplex complexity with silence and with zero is less than the classical communication complexity. This occurs for the following three functions, which are widely studied in communication complexity: the equality function $\mathrm{EQ}_n$, the disjointness function $\mathrm{DISJ}_n$ and the inner product $\mathrm{IP}_n$. These functions are defined on bit strings of length $n$ as follows:
$$
\begin{equation*}
\mathrm{EQ}_n(x,y)=\begin{cases} 1& \text{if }x=y,\\ 0& \text{otherwise}, \end{cases} \qquad \mathrm{DISJ}_n(x,y)=\bigwedge_{i=1}^n \lnot(x_i\land y_i)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\mathrm{IP}_n(x,y)=\sum_{i=1}^n( x_i\land y_i)\pmod2.
\end{equation*}
\notag
$$
The classical communication complexity of all these functions is $n+1$. The best known upper bounds for their half-duplex complexity are shown in Table 1. Table 1
The best known lower bounds are shown in Table 2. Table 2
Some cells in Tables 1 and 2 contain references showing who established the corresponding bounds. The bounds with no reference, apart from the estimates for $\mathrm{IP}_n$ with silence1 and with zero2 were obtained in [2]. However, no examples of functions for which half-duplex complexity with adversary is less than the classical complexity were known so far. Moreover, in [10], p. 67, it was conjectured that these two complexities coincide. In this paper we exhibit a function $f$ with a constant gap between these complexities (the half-duplex complexity with adversary is 5, and the classical complexity is 6). Also, we exhibit a family of partial functions $g_n$ with a logarithmic gap between these complexities. More specifically, the function $g_n$ is defined on length $n$ strings over a fixed alphabet, its half-duplex complexity with adversary is at most $n$, while the classical complexity is at least $n+\log_2n$. To prove the bound 6 for the classical complexity of $f$ and the bound ${n+\log_2n}$ for the classical complexity of $g_n$, we use some interesting techniques. The first bound cannot be proved using the standard techniques, which are based on partitions of the matrix of $f$ into monochromatic rectangles. A matrix of a function $f\colon {X\times Y}\to Z$ is a matrix with $|X|$ rows numbered by elements of $X$ and $|Y|$ columns numbered by elements of $Y$. Its element in the $x$th row and $y$th column is equal to $f(x,y)$. A monochromatic rectangle in this matrix is a subset of $X\times Y$ that has the form $A\times B$ and on which $f$ is constant. One can show that any communication protocol of depth $d$ computing $f$ provides a partition of this matrix into at most $2^d$ monochromatic rectangles. Hence the classical complexity of $f$ can be bounded below by the binary logarithm of the minimum possible number of rectangles in a partition of matrix of $f$ into monochromatic rectangles. Usually, lower bounds for the size of such partitions are obtained by means of ‘fooling sets’. A set $F\subset X\times Y$ is said to be fooling for $f$ if every monochromatic rectangle can cover at most one pair in $F$. Obviously, in this case the matrix of $f$ cannot be partitioned into fewer than $|F|$ monochromatic rectangles. So to prove that the classical complexity of $f$ is larger than $d$, it is sufficient to find a fooling set for $f$ of size larger than $2^d$. However, the matrix of our function $f$, whose classical complexity is at least 6, can be partitioned into $2^5$ monochromatic rectangles, thus this method fails to show that the classical complexity of $f$ is at least 6. To prove the required lower bound we will use the following feature of partitions derived from communication protocols: every such partition can by obtained by a sequence of horizontal and vertical divisions. More precisely, we start with the trivial partition $P=\{X\times Y\}$ and at each step we partition any rectangle in $P$ either horizontally (a rectangle ${A\times B}$ is replaced by two rectangles $A_0\times B$ and $A_1\times B$), or vertically (a rectangle $A\times B$ is partitioned into $A\times B_0$ and $A\times B_1$). If initial protocol has depth $d$, then each rectangle in the resulting partition is obtained from the original one by at most $d$ such divisions. For the required estimate we show that for every horizontal partition of the matrix of $f$ into two sub-matrices $V$ and $W$ either $U$ or $V$ has a fooling set of size $17>2^4=16$. This is done using the following method: in the matrix of $f$ we distinguish so-called ‘fooling rectangles’. They are pairwise disjoint and have the following feature: if we pick a cell from every fooling rectangle, then the resulting set of cells is a fooling set in the matrix. The number of fooling rectangles is $25$, thus this means only that the matrix has a fooling set of size $25\leqslant 2^5$. We show however that for every horizontal partition of the matrix into two sub-matrices $V$ and $W$ one of them intersects at least $17$ fooling rectangles. To do this we consider the graph whose vertices are fooling rectangles and edges connect those rectangles $R_1$ and $R_2$ that share a row. Then we prove that this graph has a certain expansion property. More specifically, every subset of $25-16=9$ vertices in the graph has at least $17$ neighbours (every vertex is a neighbour of its own). This implies the required property. Indeed, let $\mathcal R$ denote the family of all fooling rectangles that share a row with $V$. If $|\mathcal R|\leqslant 16$, then its complement $\overline{\mathcal R}$ has at least $9$ rectangles and therefore at least $17$ neighbours, and all of them share a row with $W$! Then we prove a similar statement for vertical partitions by using other fooling rectangles. To prove the lower bound $n+\log_2n$ for the communication complexity of $g_n$, we generalize the notion of a monochromatic rectangle to partial functions. This time we call a rectangle $A\times B$ monochromatic if $f$ is constant in each row and each column of $A\times B$ (at the points where it is defined). Note that if $f$ is not total, then it can still be nonconstant in the whole rectangle $A\times B$. However, for total functions this definition coincides with the classical definition of monochromatic rectangles. The matrix of our function $g_n$ can be covered by $2^n$ monochromatic rectangles. However, we show that every partition of it into monochromatic rectangles has at least $n2^n$ rectangles. The next section contains the main definitions. In § 3 we study partial functions, and in §§ 4 and 5 we study total functions. Section 4 is a ‘warming up’ section, we present there an example of a total function with a gap between the classical complexity and half-duplex complexity with a so-called ‘honest’ adversary (an honest adversary sends the same bits to both players in every silent round, but these bits can depend on the round). In § 5 we present our function $f$ with a gap between the classical and half-duplex complexities (6 versus 5). § 2. PreliminariesDefinition 1 (see [11]). A (classical) communication protocol to compute a partial function $f\colon X\times Y\to Z$ is a finite rooted tree $T$ each of whose internal nodes (including the root) has two children. Its leaves are labelled by elements of $Z$, and each internal node $v$ (including the root) is labelled either by the letter A and some function from $X$ to $\{0,1\}$, or by the letter B and some function from $Y$ to $\{0,1\}$. In addition, one outgoing edge from $v$ is labelled by 0 and the other is labelled by 1. A protocol of depth 3 to compute some function $f\colon\{0,1\}^3\times \{0,1\}^3\to\{1,2,3,4\}$ is shown in Figure 1. Each internal node is labelled by a letter indicating the turn to move and by a function computing the bit to send. For instance, if Alice has the string $x=010$ and Bob the string $y=110$, then in the first round Alice sends 1, in the second round Alice sends 0, and in the third round Bob sends 1. Then both parties output 4. Definition 2. The computation of a protocol for the input pair $(x,y)\in X\times Y$ runs as follows. At the start, the players, Alice who has $x$ and Bob who has $y$, place their tokens on the root of the tree. Then they move them along edges in the following way. If the tokens are at an internal vertex $u$ labelled by $\mathtt{A}$ and a function $h$, then they move the tokens along the edge labelled by $h(x)$. To do this Alice sends $h(x)$ to Bob, letting him know where to move his token. If the tokens are at an internal vertex $u$ labelled by $\mathtt{B}$ and a function $h$, then the tokens move along the edge labelled by $h(y)$. Finally, if the tokens come to a leaf, then the label of this leaf is the result of the computation. Definition 3. The sequence of sent bits (= the leaf to which the token comes) is called the transcript of the communication. A communication protocol computes a partial function $f\colon X\times Y\to Z$ if for all input pairs $(x,y)$ in the domain of $f$ the result of the computation is equal to $f(x,y)$. The minimum depth of a communication protocol to compute $f$ is called the communication complexity of $f$. In what follows we use the following well-known facts (see, for example, [9]) about communication protocols to compute total functions. $\bullet$ Let $\Pi$ be a communication protocol. For every node $u$ of $\Pi$ the set of input pairs $(x,y)$ such that the token comes through $u$ is a (combinatorial) rectangle, that is, it has the form $A_u\times B_u$ for some $A_u\subset X$ and $B_u\subset Y$. If $u_0$ and $u_1$ are children of $u$ and $u$ is labelled by A, then $A_u=A_{u_0}\cup A_{u_1}$ and $B_u=B_{u_0}=B_{u_1}$. In this case we say that the rectangles $A_{u_0}\times B_{u_0}$ and $A_{u_1}\times B_{u_1}$ are obtained from $A_u\times B_u$ by a horizontal division. If $u$ is labelled by B, then $B_u=B_{u_0}\cup B_{u_1}$ and $A_u=A_{u_0}=A_{u_1}$. In this case we say that $A_{u_0}\times B_{u_0}$ and $A_{u_1}\times B_{u_1}$ are obtained from $A_u\times B_u$ by a vertical division. $\bullet$ If $f$ is constant in a rectangle $R$, then $R$ is called a monochromatic rectangle for $f$. $\bullet$ If a protocol $\Pi$ computes a total function $f$, then the rectangle corresponding to any leaf of the protocol is monochromatic for $f$. Hence to each protocol computing $f$ we can assign a partition of $X\times Y$ into monochromatic rectangles. This partition has at most $2^{\text{depth of the protocol}}$ rectangles. Thus the communication complexity is at least the binary logarithm of the minimum size of the partition of $X\times Y$ into monochromatic rectangles. $\bullet$ A set $F\subset X\times Y$ is called a fooling set for a function $f\colon X\times Y\to Z$ if for all different pairs $(x,y),(u,v)\in F$ not all values $f(x,y),f(u,v),f(x,v)$ and $f(u,y)$ are equal. In this case every partition of $X\times Y$ into monochromatic rectangles contains at least $|F|$ rectangles. The definition of a half-duplex communication protocol is more complicated. Definition 4 (see [2]). A half-duplex communication protocol to compute a partial function $f\colon X\times Y\to Z$ is a pair of rooted trees $T_A$, $T_B$. Each internal node of both trees has four children. Each internal vertex $v$ of $T_A$ is labelled by a function from $X$ to the three-element set consisting of the actions ‘send 0’, ‘send 1’ and ‘receive’. Edges outgoing from $v$ are labelled by the events ‘sent 0’, ‘sent 1’, ‘received 0’ and ‘received 1’. Similarly, each internal vertex of $T_B$ is labelled by a function from $Y$ to the set of actions, and outgoing edges are labelled by events. Leaves of both trees are labelled by elements of $Z$. The computation for an input pair $(x,y)\in X\times Y$ runs as follows. First, for each internal vertex of both trees we calculate the action of the player by applying the corresponding function to her/his input ($x$ or $y$). Second, each player puts a token on the root of her/his tree and moves it in accordance with the following rules. If the tokens are at vertices $u$ and $v$, and the actions of the players at these nodes are $a$ and $b$, respectively, then the tokens are moved as shown in Table 3. Table 3
If both players chose to receive (the last row of Table 3) then the round is said to be ‘silent’. In this case the received values $i$ and $j$ are chosen by an adversary, who decides where the tokens are moved to. The computation stops when one of the token reaches a leaf. The result of the computation is defined as follows. If the other token is not in a leaf, then the result is undefined. If both tokens reach leaves but their labels are different, then the result is also undefined. Finally, if these labels coincide, then that label is the result of computation. An example of a 1-round half-duplex protocol is shown in Figure 2. Here we assume that $X=Y=\{0,1,2\}$ and $Z=\{0,1\}$. The event ‘sent $i$’ is abbreviated as s$i$ and similarly the event ‘receive $i$’ is abbreviated as r$i$. The letter $g$ denotes the map $0\mapsto \text{send 0}, 1\mapsto \text{send 1}, 2\mapsto \text{receive}$, and $h$ denotes the same map. This protocol computes a function $f\colon\{0,1,2\}\times \{0,1,2\}\to\{0,1\}$ which is defined only at the pairs $(0,0)$, $(1,1)$ and $(1,2)$. At the first and second pair both players send a bit which is lost; however, they output the same result. At the third pair Alice sends 1, which is received by Bob, who actually does not care since he outputs 1 anyway. Definition 5. A half-duplex protocol computes a function $f$ if for all pairs $(x,y)$ in its domain and for all choices of the received bits in silent rounds (in different silent rounds different pairs $(i,j)$ can be chosen) the computation ends with the result $f(x,y)$. If $f(x,y)$ is undefined, then the computation can end with any result or without any result. Definition 6. There is a natural variation of computation using a half-duplex protocol, in which the adversary sends the same bits to Bob and Alice in each silent round (this bit can depend on the round). Such an adversary is called honest. To distinguish original communication protocols and complexity from half-duplex ones we call the former classical. Remark 1. Classical protocols can be viewed as a particular case of half-duplex protocols. To convert a classical protocol into a half-duplex one, we first transform its tree $T$ as follows. For each internal vertex $v$ of $T$ we make two copies of the tree with root in the left-hand child of $v$ and two copies of the tree with root in the right-hand child of $v$. The edge going to the first copy of the left-hand child is labelled by the event ‘sent 0’, and the edge going to the second copy of the left-hand child is labelled by the event ‘received 0’, and similarly for the right-hand child. This transformation must by applied to all internal nodes in any order. The trees $T_A$ and $T_B$ are equal to the resulting trees. If an internal node $v$ is labelled by $\mathtt{A}$ and $h$ in $T$, then in Alice’s tree $T_A$ all copies of $v$ are marked by the function that maps $x$ to the action ‘send $h(x)$’, and in Bob’s tree $T_B$ by the constant function ‘receive’. Similarly, if $v$ is labelled by $\mathtt{B}$ and $h$ in $T$, then in Bob’s tree all copies of $v$ are labelled by the function mapping $y$ to ‘send $h(y)$’, and in Alice’s tree by the constant function ‘receive’. By construction there are no silent or wasted rounds in the computation of the resulting protocol. The half-duplex complexity with honest adversary is obviously less than or equal to the half-duplex complexity with ordinary adversary, and the latter is less than or equal to the classical communication complexity. One can also show that the half-duplex complexity with either adversary is larger than or equal to one half of the classical complexity [2].3 § 3. Separation of the half-duplex and classical communication complexities for partial functions3.1. An exampleLemma 1. There is a partial function $g$ whose half-duplex complexity is $1$ and classical complexity is at least $2$. Proof. Let $X = Y = \{0, 1, \mathtt{r}\}$ and $Z =\{0\mathtt{r},1\mathtt{r},\mathtt{r}0,\mathtt{r}1\}$, and let the partial function $g\colon X\times Y \to Z$ be defined by Table 4.
The classical complexity of $g$ is at least $2$: in any protocol of depth $1$ either Alice sends a bit (and so she outputs the same result for the input pairs $(\mathtt{r},0)$ and $(\mathtt{r},1)$), or Bob sends a bit, and so he outputs the same results for the input pairs $(0, \mathtt{r})$ and $(1,\mathtt{r})$. The half-duplex complexity of $g$ is at most $1$. The protocol is as follows: Alice sends $0$ for the input $0$ and outputs $0r$, and for the input $1$ she sends $1$ and outputs $1\mathtt{r}$. Finally, for the input $\mathtt{r}$ she receives and after receiving $z$ she outputs $\mathtt{r} z$. Bob acts in a similar way: for the input $0$ he sends $0$ and outputs $\mathtt{r}0$, for the input $1$ he sends $1$ and outputs $\mathtt{r}1$, and for the input $\mathtt{r}$ he receives, and after receiving $z$ he outputs $z \mathtt{r}$. The lemma is proved. Consider the following generalization of this function, which provides a linear gap between half-duplex and classical complexities. Let $X = Y = \{0, 1, \mathtt{r}\}^n$ and $Z =\{0\mathtt{r},1\mathtt{r},\mathtt{r}0,\mathtt{r}1\}^n$; then we define $g$ as follows: $g(x,y)$ is defined if $x_i = \mathtt{r} \wedge y_i \neq r$ or $x_i \neq \mathtt{r} \wedge y_i = \mathtt{r}$ for all $i$. In this case the $i$th symbol of $g(x,y)$ equals $\mathtt{r} y_i$ in the first case and equals $x_i\mathtt{r}$ in the second. That is, if Alice’s and Bob’s inputs are ‘consistent’ (in each position one party has and the other has 0 or 1), then the function is defined, and otherwise it is not. Theorem 1. (a) The half-duplex complexity of $g$ is at most $n$. (b) The classical complexity of $g$ is at least $2n$. Proof. (a) In the $i$th round, independently on what happened in the previous rounds, each party receives if her/his $i$th symbol is otherwise she/he sends $i$th symbol of the input.
As the $i$th symbol of the output Alice takes if in the $i$th round she sent a bit (equal to $x_i$), and she takes $\mathtt{r} y_i$, if she received $y_i$. Bob acts in a similar way. If their inputs are consistent, then they output the same result, which is moreover equal to the value of the function. (b) Note that the function $g$ has $4^n$ possible values, hence any classical communication protocol computing $g$ must have at least $4^n$ leaves. Thus, its classical communication complexity is at least $\log_2 4^n=2n$. The theorem is proved. 3.2. Local communication complexityThere is a way to compute the function $g$ from § 3.1 by communicating at most $n + \lceil \log_2(n + 1)\rceil$ bits.
Why this protocol does not contradict the lower bound $2n$ for the communication complexity of the function $g$? This is because this protocol is not a communication protocol in accordance with Definition 4. Indeed, Alice and Bob form their outputs based not only on the transcript of computation but also on their inputs. As we will see below, for total functions this possibility does not yield anything new. However, for partial functions this possibility can reduce the communication complexity, as our example shows. A simpler example of this phenomenon is presented below. For this reason, for partial functions a more adequate communication model should allow players to use their inputs when computing the output. As far as we know, such a communication model appeared quite recently in [8], p. 58. Let us define it more formally. Definition 7 (see [8]). A local communication protocol for a function $f\colon X \times Y \to Z$ is a communication protocol in which each leaf is labelled by a pair of functions ${X \to Z}$ and $Y \to Z$. If the computation for an input pair $(x, y)$ has ended at a leaf labelled by a pair of functions $(p,q)$, then the result of the computation is defined to be $p(x)$, provided that $p(x) = q(y)$, and it is undefined otherwise. A local communication protocol computes a partial function $f\colon X \times Y \to Z$ if for all input pairs $(x,y)$ in its domain this protocol outputs $f(x,y)$ (the result can be defined and undefined alike for pairs outside the domain of the function). The local communication complexity of a function is the minimum depth of a local communication protocol computing this function. Local half-duplex communication protocols and the local half-duplex communication complexity are defined in a similar way. When we want to distinguish local protocols from regular ones, we call the latter global. 3.3. An exampleConsider the partial function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ defined by
$$
\begin{equation*}
f(x,y)=\begin{cases} x &\text{if }x=y,\\ \text{undefined}& \text{if }x\ne y. \end{cases}
\end{equation*}
\notag
$$
Since $f$ takes $2^n$ different values, any global (classical) protocol for it has at least $2^n$ leaves, and so its depth is at least $n$. Thus the global (classical) complexity of $f$ is at least $n$. On the other hand the local (classical) complexity of $f$ is $0$: label the root of $T_A$ and $T_B$ with $h(x) = x$ (each player just outputs her/his input). It is important in this example that the function is not total. There are no such examples for total functions in classical or half-duplex models alike. 3.4. The local and global complexity of total functionsLemma 2. For classical communication complexity, the local complexity of a total function is equal to its global complexity. Proof. Given a local (classical) communication protocol for $f$, let $l$ be a leaf of it. Let $R_l=A_l\times B_l$ denote the rectangle consisting of all input pairs $(x,y)$ for which the computation reaches $l$, and let $p_l$ and $q_l$ be the output functions labelling this leaf. Then for all $x\in A_l$ and $y\in B_l$ we have $p_l(x)=q_l(y)$, which shows that $p_l$ and $q_l$ are constants (of course, provided that the set $R_l$ is nonempty). Hence any local protocol to compute a total function can be converted into a classical protocol of the same depth just by replacing the label $(p_l,q_l)$ by the constant value of $f$ on $R_l$.
The lemma is proved. A similar fact holds for half-duplex complexity. Lemma 3. For half-duplex communication complexity, the local complexity of a total function is equal to its global complexity. Proof. The proof is similar to the proof of the previous lemma. However, we cannot use now the argument involving combinatorial rectangles because the rectangles corresponding to leaves of Alice’s and Bob’s trees can be distinct.
We show that each local protocol to compute a total function is essentially global. More precisely, all computations ending at the same leaf output the same result. Replacing the function labelling each leaf by the output result, we transform a local protocol to a global protocol of the same depth that calculates the same function. Consider a local communication protocol $(T_A, T_B)$ to compute a total function $f$. Assume that for an input pair $(x, y)$ the computation can end at leaves $(a,b)$ and for another input pair $(x',y')$ Alice’s computation can end at the same leaf $a$. Let us show that for the input pair $(x', y)$ the computation can also end at the leaves $(a, b)$. Let $a_i$ and $b_i$ denote the $i$th vertices on the paths from the roots to $a$ and $b$, respectively. Since Alice’s computation for both inputs $(x, y)$ and $(x', y')$ can end at the leaf $a$, for all $i$ Alice’s action at the vertex $a_i$ for the inputs $x$ and $x'$ is the same. Thus, if the adversary’s action in the computation for the input pair $(x', y)$ is identical to that for the input $(x, y)$, when the computation ends at $(a, b)$, then both players in each round perform the same actions for the inputs $(x, y)$ and $(x', y)$, and all events are also identical. Hence the computation can also end at the same leaves $(a, b)$. Let the leaf $a$ be labelled by a function $p$ and the leaf $b$ by a function $q$. Then $p(x) = f(x, y) = q(y) = f(x', y) = p(x')$. (It is important here that $f$ is a total function, as otherwise $ f(x', y)$ can be undefined, and then $q(y)$ can differ from $p(x')$.) Thus each leaf of $T_A$ is labelled by a function that is constant on all the $x$ for which the computation can end at this leaf for some $y$. Now we transform $(T_A, T_B)$ into a global protocol of the same depth which calculates $f$. To do this, in each leaf $a$ of $T_A$ at which we can occur for some input $(x, y)$ we replace the function labelling this leaf by its value at $x$. For a leaf where we cannot occur we replace the function labelling it by an arbitrary constant. We deal similarly with $T_B$. Then we obtain a classical protocol $(T'_A, T'_B)$ of the same depth, which for each input outputs the same result as $(T_A, T_B)$ (for the same actions of the adversary) and therefore calculates the same function. The lemma is proved. 3.5. The local classical complexity of the function $g$For partial functions, local protocols seem to be a more natural communication model than the global ones. In the introduction, before giving a formal definition we talked about the lower bound $n+\log_2n$ for the classical communication complexity of the function $g_n$. We meant there the local complexity. Now we prove this statement. Theorem 2. (a) The local classical complexity of $g$ is at most $n + \lceil \log_2(n + 1)\rceil$. (b) The local classical complexity of $g$ is at least $n + \lceil\log_2 n\rceil - \log_2 3 + o(1)$. Lemma 4. If the local classical complexity of a partial function $g$ is at most $c$, than its matrix can be partitioned into at most $2^c$ rectangles with the following property: if two inputs $(x, y)$ and $(x, y')$ occur in the same rectangle, and $g$ is defined for both of them, then $g(x, y) = g(x, y')$, and similarly, if two inputs $(x, y)$ and $(x', y)$ occur in the same rectangle and $g$ is defined for both of them, then $g(x, y) = g(x', y)$. (Rectangles with this property will be called monochromatic.) Proof. Leaves of a classical communication protocol define a partition of the matrix into rectangles. Each of these rectangles has the required property: if a function $p$ is written in Alice’s leaf and $g$ is defined for $(x, y)$ and $(x, y')$, then we necessarily have $g(x, y) = p(x) = g(x, y')$, and similarly for Bob.
If the depth of the protocol is $c$, then the number of leaves is at most $2^c$, and the corresponding rectangles form the required partition. The lemma is proved. We any input of the form $(\{0, 1\}^k \mathtt{r} ^{n - k}, \mathtt{r} ^m \{0, 1\}^{n - m})$ simple. We denote by $[x]$ the total number of symbols $0$ and $1$ in $x$. We colour light grey all simple inputs $(x, y)$ such that $[x] + [y] = n$. The function $g$ is defined for such inputs. We colour dark grey simple inputs $(x, y)$ such that $[x] + [y] < n$. The function $g$ is not defined for them (see Figure 3). The number of light grey inputs is $(n + 1) \cdot 2^n$. The number of dark grey inputs is
$$
\begin{equation*}
\sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - i - 1} 2^{i + j} = \sum_{i = 0}^{n - 1} 2^i (2^{n - i} - 1) = n 2^n - (2^n - 1) = (n - 1) 2^n + 1.
\end{equation*}
\notag
$$
Assume that the classical complexity of $g$ is at most $c$. We apply Lemma 4 to a classical protocol of depth $c$ to compute $g$ and consider the corresponding partition into at most $L=2^c$ monochromatic rectangles. Let $(x, y)$ and $(u, v)$ be different light grey inputs such that $[x] = [u]$. Then $g$ is defined on both $(x, v)$ and $(u, y)$ and not all values $g(x, y)$, $g(x, v)$, $g(u, y)$ and $g(u, v)$ are the same. Thus, $(x, y)$ and $(u, v)$ lie in different rectangles of the partition. Note that if a rectangle contains $k$ light grey inputs $(x_i, y_i)$, ${[x_1] \!<\! [x_2] \!<\! \cdots \!<\! [x_k]}$, then it also contains $k(k - 1)/2$ dark grey inputs $(x_i, y_j)$, $i < j$. Let $k_i$ be the number of light grey inputs in the $i$th rectangle; then the $i$th rectangle also contains at least $k_i (k_i - 1)/2$ dark grey inputs. Then $\sum_{i=1}^L k_i = (n+1)2^n$. On the other hand $\sum_{i = 1}^L k_i (k_i - 1)/{2} \leqslant (n - 1) 2^n + 1$ as the rectangles are disjoint. Re-writing the second inequality we obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{i = 1}^L( k_i^2 - k_i) &\leqslant (2n - 2) 2^n + 2, \\ \sum_{i = 1}^L k_i^2 &\leqslant (2n - 2) 2^n + 2 + (n + 1) 2^n \\ &= (3n - 1) 2^n + 2. \end{aligned}
\end{equation*}
\notag
$$
By the Cauchy–Schwarz inequality $(\sum_{i=1}^L k_i)^2 \leqslant L \sum_{i=1}^L k_i^2$. Therefore,
$$
\begin{equation*}
\begin{aligned} \, &(n + 1)^2 2^{2n} \leqslant L ((3n - 1) 2^n + 2)\quad\Longrightarrow \quad L \geqslant \frac{(n + 1)^2 2^{2n}}{(3n - 1) 2^n + 2} \\ &\quad\Longrightarrow\quad L \geqslant \frac{n 2^n}{3}(1 + o(1))\quad\Longrightarrow \quad c=\log_2 L \geqslant n + \log_2 n - \log_2 3 + o(1). \end{aligned}
\end{equation*}
\notag
$$
The theorem is proved. Thus, the function $g$ is an example of a partial function with a linear gap between the global classical and half-duplex complexities, and with a logarithmic gap between the local classical complexity and half-duplex complexities. We would also like to find an example of a total function with the same gap. As we saw, for total functions the local and global complexities coincide, thus we mean here a logarithmic gap. Unfortunately, we could not find such an example. In the rest of the paper we present an example of a total function with a constant gap, namely, the gap between 5 and 6 We will start with a simpler example of a constant gap between the classical complexity and half-duplex complexity with honest adversary. § 4. The half-duplex complexity with honest adversary can be less than the classical complexity for total functionsTheorem 3. There is a total function with classical complexity 4 and half-duplex complexity with honest adversary at most 3. Proof. Let $X=Y=\{\mathtt{r},00,01,10,11\}$ and $Z=\{0,1,2\}$. First we design a three-round half-duplex protocol computing a total function $f\colon X\times Y\to Z$ (against an honest adversary), and then we prove that its classical complexity is at least 4.
In this protocol only the first round is not classical. In this round both players depending on their inputs choose one of the three actions. This action is determined by the first symbol of the input: $\mathtt{r}$ means ‘receive’, and $0$ and $1$ mean ‘send $0$ or $1$’, respectively. In the second round Bob sends a bit and Alice receives, and in the third round the other way around. In these two rounds the players send the bit that was received in the first round, provided they chose to receive in the first round. Otherwise players send the second bits of their inputs. The result of the protocol is a function of bits sent (and received) in the second and third rounds (we call it the 2–3-transcript in what follows). Since these rounds are classical, this guarantees that Alice and Bob output the same result, whatever happens in the first round. Let us see what the 2–3-transcript is equal to. If Bob’s input is $\mathtt{r}$ and Alice’s input is $0$, $1$, then the 2–3-transcript coincides with Alice’s input. Similarly, if Bob’s input is distinct from $\mathtt{r}$ and Alice’s input is $r$, then the 2–3-transcript coincides with Bob’s input reversed. If both Alice’s and Bob’s inputs are distinct from $\mathtt{r}$, the 2–3-transcript is formed from the second bits of Bob and Alice (in this order). Finally, if both Alice’s and Bob’s inputs are equal to $\mathtt{r}$, then the 2–3-transcript consists of the bits chosen by the adversary. The 2–3-transcript is shown in Table 5, where Alice’s input indicates the row and Bob’s input indicates the column. We see that there are two possible transcripts for the input pair $(\mathtt{r},\mathtt{r})$ (rather then four, because we assume that the adversary is honest). Thus, in order that the transcript compute a total function, it is sufficient that the output function is the 2–3-transcript itself with identified 00 and 11. Representing 2–3-transcripts by natural numbers whose binary notations they output we obtain the function in Table 6. The key point is as follows: if the adversary is honest and sends the same bit to Alice and Bob in a silent round, then the transcript is equal to 00 or 11, and we need to identify only these two transcripts. Otherwise the transcripts can be equal to any two-bit sequence, so the function is trivial. It is easy to show that the classical complexity of the function defined is at least 4, To do this we indicate a fooling set of 10 pairs. They are printed bold in the matrix:
$$
\begin{equation*}
\begin{pmatrix} 0&0&\boldsymbol 2&\boldsymbol 1&\boldsymbol 0 \\ \boldsymbol 0&0&2&0&\boldsymbol 2 \\ \boldsymbol 1&1&0&1&0 \\ \boldsymbol 2&\boldsymbol 0&2&0&2 \\ 0&\boldsymbol 1&\boldsymbol 0&1&0 \end{pmatrix}
\end{equation*}
\notag
$$
The theorem is proved. Recently Kuptsov showed (a private communication of 2023) that the half-duplex complexity with malicious adversary of this function is the same as its classical complexity, that is, it is equal to 4. Thus this function separates the half-duplex complexity with adversary from the half-duplex complexity with honest adversary. This also means that to separate the half-duplex complexity with ordinary adversary from the classical complexity we have to look for another example. Since fooling sets have the direct product property, this example is provided by a sequence of functions with a linear gap between half-duplex complexity with honest adversary and classical complexity. More specifically, let the function $f^n\colon {X^n\times Y^n\to Z^n}$ be the direct product of $n$ copies of $f$, that is, $f^n(x_1x_2\dots x_n,y_1y_2\dots y_n)=f(x_1,y_1)f(x_2,y_2)\dotsb f(x_n,y_n)$. Here $X$, $Y$, $Z$ and $f$ are the sets and function from the proof of the previous theorem. The arguments of $f$ are length $n$ strings over the alphabets $X$ and $Y$, and its value is a length $n$ string over $Z$. Theorem 4. The classical complexity of $f^n$ is at least $n\log_210$, while its half-duplex complexity with honest adversary is at most $3n$. Proof. The second statement is obvious since we can just apply $n$ times the protocol from the previous theorem to compute $n$ copies of $f$. The lower bound for classical complexity is proved as follows. Recall that the function $f$ has a fooling set $F$ of size 10. We claim that its Cartesian power $F^n$ is a fooling set for $f^n$.
For a contradiction assume that that two different pairs $(x,y)$ and $(a,b)$ belong to $F^n$ and lie in a monochromatic rectangle $R$. Let $x=x_1\dots x_n$, $y=y_1\dots y_n$, $a=a_1\dots a_n$ and $b=b_1\dots b_n$. Then for some $i$ the pairs $(x_i,y_i)$ and $(a_i,b_i)$ are different. Without loss of generality assume that $i=1$. Since $F$ is a fooling set for $f$, the rectangle $\{x_1,a_1\}\times\{y_1,b_1)$ is not monochromatic. That is, this rectangle has two pairs at which $f$ has different values. There are six possible cases. Case 1: Assume first that $f(x_1,y_1)\ne f(a_1,b_1)$. Then $f(x,y)\ne f(a,b)$, which is a contradiction, as both the pairs $(x,y)$ and $ (a,b)$ are in $R$. Case 2: Now assume that $f(x_1,y_1)\ne f(x_1,b_1)$. Then $f(x,y)\ne f(x,b)$, which is again a contradiction, as both the pairs $(x,y)$ and $ (x,b)$ are in $R$. The remaining cases are similar to these two. Since $|F^n|=10^n$, the classical complexity of $f^n$ is at least $\log_2|F^n|=n\log_210$. § 5. The half-duplex complexity with adversary can be less that the classical complexityTheorem 5. There is a total function with classical complexity 6 and half-duplex complexity (with adversary) at most 5. The proof of this theorem is similar to the proof of Theorem 4 but it is much more complicated. The proof is divided into three parts. In § 5.1 we define a 5-round half-duplex protocol $\Pi$ to compute a total function. In §§ 5.1 and 5.2 we prove that the classical complexity of the function in question is at least 6. 5.1. The half-duplex protocol5.1.1. A general protocolOur general plan is as follows. The first round of the protocol $\Pi$ is not classical and all the remaining four rounds are classical; in these rounds the players send bits in the following order: Bob, Alice, Bob, Alice. The result of the protocol is a function of quadruples of bits sent in rounds 2–5 (this sequence will called a 2–5-transcript). The inputs of players consist of one or two symbols. The first symbol of a player’s input has the same meaning as before: it indicates what to do in the first round. The second symbol indicates what to do after that. More specifically, Bob’s input is either $\mathtt{r}$, or has the form $0\phi$ or $1\phi$, where the range of $\phi$ will be defined below. Alice’s input is either $\mathtt{r}\eta$, or has the form $0\psi$ or $1\psi$, where the ranges of $\eta$ and $\psi$ will be defined below. The protocol is as follows. 1. If Bob’s input is $\mathtt{r}$, then in the first round Bob receives, then he sends the bit he has just received, then receives again, then he sends the bit received in the first round again, and then receives again. 2. If Alice’s input is $\mathtt{r}\eta$, then she receives in the first round, then she receives again (we denote the received bit by $i$), then sends the bit from the first round, then receives again (let this bit be $k$), then sends the bit from the first round again if $i=k$. Otherwise (if $i\ne k$), in the last round Alice sends a bit that depends on $\eta$, $i$ and $k$ (we describe this dependence below). 3. If Bob’s input is $i\phi$, then Bob sends $i$ in the first round, then he sends a bit depending on $\phi$, then receives (let this bit be $j$), then sends a bit that depends on $j$ and $\phi$, and then receives a bit again. 4. If Alice’s input is $j\psi$, then Alice sends $j$ in the first round, then she receives (let this bit be $i$), then sends a bit depending on $i$ and $\psi$, then receives (let this bit be $k$), and she finally sends a bit depending on $i$, $k$ and $\psi$. According to this protocol, for the input pair $(\mathtt{r}\eta, \mathtt{r})$ the events of the players are as shown in Table 7 (provided that the adversary sends $j$ to Alice and $i$ to Bob in the first round). Table 7
So far, this is only a general plan of the construction of the protocol. We have yet to define the ranges of $\eta$, $\phi$ and $\psi$ and to define the dependencies mentioned above. However, we can already see that if the first round happens to be silent (that is, both inputs begin with $\mathtt{r}$), then the 2–5-transcript of the protocol is one of the four sequences 0000, 0101, 1010 and 1111. In fact, in this case both player send twice the bits obtained from the adversary in the first round. We define Alice’s and Bob’s outputs to be be 0 if the 2–5-transcript of the protocol is one of these four sequences, and to the 2–5-transcript otherwise. In other words, we identify all 2–5-transcripts of the form $abab$. Such a definition guarantees that even for a malicious adversary the function computed is total. We have identified only a quarter of the 2–5-transcripts, which leaves an opportunity for the function computed to be nontrivial. 5.1.2. The first realization of the planThe simplest realization of this plan is as follows: let $\eta=0,1$ and $\phi,\psi\in\{00,01,10,11\}$, and let the protocol run as follows. 1. If Bob’s input is $\mathtt{r}$, then in the first round Bob receives (let $m$ denote the received bit), then he sends $m$, then receives again, then he sends $m$ again, and then he receives again. 2. If Alice’s input is $\mathtt{r}\eta$, then she receives in the first round (let $m$ denote the received bit), then she receives again (let this bit be $i$), then sends $m$, then receives again (let this bit be $k$), then sends $m$ again if $i=k$ and sends $\eta$ otherwise. 3. If Bob’s input is $i\phi$, where $i=0,1$ and $\phi=\phi_1\phi_2$, then Bob sends $i$ in the first round, then he sends $\phi_1$, then receives, then sends $\phi_2$, then receives again. 4. If Alice’s input is $j\psi$, where $j=0,1$ and $\psi=\psi_1\psi_2$, then Alice sends $j$ in the first round, then she receives, then sends $\psi_1$, then receives, and finally she sends $\psi_2$. As a result of the communication between Alice and Bob we obtain the matrix presented in Table 8 (where transcripts are represented by the integers with binary expansions equal to these transcripts). Thus our protocol computes the function with the following matrix (zeros are rendered by different fonts indicating the corresponding 2–5-transcripts):  By construction the half-duplex complexity of this function is at most 5. Unfortunately, its classical complexity is also at most 5. To show this, let us note that this matrix has seven different columns (the second column coincides with the sixth and the fifth column with the ninth). Each column of this matrix, except the first, contains at most four different numbers. Therefore, we can compute this function in five rounds using the following protocol. First Bob lets Alice know the whole column corresponding to his input. If his input is not equal to the first column, then he sends three bits, and otherwise he sends only two bits. For example, if his input is not equal to the first column, then he uses one of the six three-bit messages 100, 101, 110, 111, 010 and 011, and otherwise he sends 00. In the first case Alice sends Bob the value of the function in two rounds. In the second case she does this in three rounds. 5.1.3. The second (and final) realization of the planTo increase the classical complexity of this function, let us use the dependencies not specified yet in the most general form. Namely, let $\phi$ range over all maps that determine which bits Bob sends in the second and fourth rounds in all possible situations. In other words, $\phi$ is a function with domain $\{\Lambda,0,1\}$ and values $0$ and $1$, where $\phi(\Lambda)$ is the bit sent in the second round and $\phi(a)$ is the bit sent in the fourth round after receiving $a$ in the third round. Thus Bob has $1+2\times 8=17$ different inputs. Similarly, $\eta$ ranges over all mappings that determine which bits Alice sends in all possible situations. The domain of $\eta$ is the set $\{001,101,010,110\}$ where $\eta(iab)$ is the bit that Alice sends in the fifth round, provided she received $i$, $a$ and $b$ in the first, second and fourth rounds, respectively. The domain of $\psi$ is $\{0,1, 00, 01,10,11\}$ where $\psi(a)$ is the bit that Alice sends in the third round, provided she received $a$ in the second round, and $\psi(ab)$ is the bit Alice sends in the fifth round, provided she received $a$ and $b$ in the second and fourth rounds, respectively. Thus Alice has $2\times 2^6+2^4=144$ different inputs. Now our half-duplex protocol is well defined. By construction it computes a total function and we denote this function by $U$. We can prove purely analytically, by looking at a few cases, that the matrix $U$ has classical complexity 6. However, this proof, as well as the matrix itself, is unwieldy, so we have attempted to delete some columns and (mainly) rows from $U$ to obtain a manageable submatrix with the same classical complexity. Note that the deletion of rows and columns does not increase the half-duplex complexity, so the half-duplex complexity of any submatrix of $U$ is at most 6. 5.1.4. Submatrices of $U$ with communication complexity $6$: the matrix $S$The smallest submatrix of $U$ with classical complexity 6 we managed to find is shown in Figure 4. We denote this submatrix by $S$. The communication complexity of $S$ was found in four minutes of computer-assisted exhaustive search using dynamic programming. Since this search cannot be performed by hand, we continued to look for a manageable submatrix of $U$ with moderately small domain for which we can prove the lower bound 6 for the classical complexity by the same method as for $U$.  Figure 4.The matrix $S$. Its classical complexity is 6, and its half-duplex complexity is at most 5. 5.1.5. Submatrices of $U$ with communication complexity $6$: the matrix $M$The matrix $M$ we found is shown in Figure 5. It is obtained from $U$ by deleting the maximum possible number of rows and columns that does not break down our analytic proof of the lower bound of 6 for the classical complexity of $U$. We explain this in greater detail slightly below. In Figure 6 we indicated, on the left and on the top, Alice’s and Bob’s inputs labelling the rows and columns left in $M$. Looking at this matrix, we can imagine how the matrix $U$ looks like. Looking at Figure 6 we can verify that each entry in the matrix is indeed the result of the half-duplex protocol $\Pi$ described above for the corresponding input pair. We can also verify that the matrices in Figures 5 and 6 are identical. This implies that the matrix in Figure 6 is a submatrix of $U$, and therefore its half-duplex complexity is at most 5. However, both verifications are quite time consuming and therefore we explain in § 5.1.6 how to verify it quicker that the half-duplex complexity of $M$ is at most 5. 5.1.6. A fast verification that the half-duplex complexity of the matrix in Figure 5 is at most $5$We exhibit the partition of the matrix from Figure 5 into monochromatic rectangles corresponding to leaves of Alice’s and Bob’s trees (in the protocol $\Pi$). Such a partition is shown in Figure 7. Double lines partition the matrix according to events in the first round. For example, the bottom right rectangle consists of all input pairs for which both Alice and Bob send 1, the upper right rectangle consists of all input pairs for which Alice receives 1 from Bob, and the upper left rectangle consists of all input pairs for which both parties receive in the first round. These rectangles are denoted by $P_{\mathtt{r}\mathtt{r}}$, $P_{\mathtt{r}0}$, $P_{\mathtt{r}1}$, $P_{0\mathtt{r}}$, $P_{1\mathtt{r}}$, $P_{00}$, $P_{01}$, $P_{10}$ and $P_{11}$. In Figure 7 we restore the 2–5-transcripts, that is, $0$, $5$, $10$ and $15$ have not yet been identified. The only exception is the rectangle $P_{\mathtt{r}\mathtt{r}}$, in which all 2–5-transcripts $0$, $5$, $10$ and $15$ can appear. The number in each cell indicates the part ($0$- or $1$-part) in which the corresponding cell falls in each round. Namely, its leading bit is equal to the bit sent by Bob in the second round, the second bit is equal to the bit sent by Alice in the third round, and so on. In the second round all numbers are divided into smaller ones (less than 8) and larger ones (larger than or equal to 8). This partition is indicated by vertical lines. In the third round the numbers are divided in accordance with their second bits: entries in the regular font contain 0 and boldface ones contain 1. In the fourth round the numbers are divided in accordance with their third bits: those with 1 as the third bit are shown in italics. Finally, in the fifth round the numbers are divided into even and odd ones. It is not hard to verify that the resulting partition corresponds to the protocol described in § 5.1.1. It is also easy to check that all rectangles in this partition are monochromatic. For example, all the five rectangles consisting of large italic odd integers are monochromatic: all their entries are equal to 11. 5.2. A lower bound for the communication complexity of $U$ and $M$It remains to estimate from below the classical complexity of the matrices $U$ and $M$. Unfortunately, we cannot prove this using partitions into monochromatic rectangles, as both matrices can be partitioned into $30\leqslant2^5$ monochromatic rectangles. These rectangles correspond to the leaves of classical protocols performed by Alice and Bob in rounds 2–5. We have $9\times 16$ such leaves (nine events in the first rounds are multiplied by the number of leaves in a classical protocol of depth 4). However, some of these rectangles can be joined together, and after that we obtain 30 monochromatic rectangles. Let us show this partition for the matrix $S$ (for $U$ and $M$ the partition is similar). For any integer $i\ne 0$ the part of the matrix consisting of the entries $i$ can by partitioned into two rectangles. For $i=1$ and $i=2$ the partition is shown in Figure 8. And the zeros can be partitioned into six rectangles as shown in Figure 9. This number (30) of monochromatic rectangles cannot be reduced, which can be shown by use of fooling sets. The proofs for $U$ and $M$ are almost identical. More specifically, some lemmas proved analytically for $U$ can by proved for $M$ by looking at pictures. We will show that for every vertical partitioning of a matrix into two parts (so that the columns are divided into two sets) at least one part contains a fooling set of size 17 (hence its communication complexity is at least 5), and a similar statement holds for horizontal partitions. 5.2.1. The proof for horizontal partitionsIn the matrix we distinguish 25 rectangles denoted by
$$
\begin{equation*}
R_0,R_1,\dots,R_4,R_6,\dots,R_9,R_{11},\dots,R_{14},S_1,\dots,S_4,S_6,\dots,S_9,S_{11},\dots S_{14}
\end{equation*}
\notag
$$
($R_5$, $R_{10}$, $R_{15}$, $S_0$, $S_5$, $S_{10}$ and $S_{15}$ are skipped). They are called fooling rectangles. All the entries of rectangles $R_i$ and $S_i$ are equal to $i$. In addition, for any two cells $u$ and $v$ from different rectangles the set $\{u,v\}$ is a fooling set for the matrix, that is, no monochromatic rectangle contains both $u$ and $v$. In other words, if we pick an arbitrary cell from every fooling rectangle, then the resulting set of cells is a fooling set. The existence of such a set of rectangles proves only that the matrix has a fooling set of size 25. However, it is characteristic for fooling rectangles that we cannot partition a matrix into two by a vertical division so that each fooling rectangle occurs in one part. Moreover, one part of such a partition intersects at least 17 fooling rectangles, so it contains a fooling set of cardinality 17. Now we define fooling rectangles. For the matrix $M$ the reader can skip the definition and look at Figure 10 instead, where the fooling rectangles are indicated by fonts. The reader need not verify the agreement between the picture and the formal definition. Definition 8 (fooling rectangles). Recall that the value of the function under consideration is essentially equal to the 2–5-transcript of the computation, which is a 4-bit sequence $abcd$. Therefore, in the definition of $R_i$ and $S_i$ it is convenient to regard $i$ as a 4-bit sequence $abcd$. First we define the rectangles $R_i$. If $a\ne c$, then Now we define the fooling rectangles $S_i$. If $a\ne c$, then
$$
\begin{equation*}
S_{abcd}=S_{ab\overline ad}= \{\mathtt{r}\eta \mid \eta(bac)=d\} \times\{b\phi\mid \phi(\Lambda)=a,\,\phi(b)=\overline a\}.
\end{equation*}
\notag
$$
Otherwise, if $a=c$, then
$$
\begin{equation*}
S_{abcd}= S_{aba\overline b}= \{a\psi\mid \psi(a)=b,\,\psi(aa)=\overline a\}\times\{\mathtt{r}\}.
\end{equation*}
\notag
$$
The first equality holds since the rectangles $S_{0000}$, $S_{0101}$, $S_{1010}$ and $S_{1111}$ have not been defined. For the reader’s convenience, here are the explicit definitions of the fooling rectangles:
$$
\begin{equation*}
\begin{aligned} \, R_0&=\{*\psi\mid \psi(0)=0,\, \psi(00)=0\} \times\{1\phi \mid \phi(\Lambda)=0,\, \phi(0)=0\}, \\ R_1&= \{1\psi \mid \psi(0)=0,\, \psi(00)=1\} \times\{*\phi\mid \phi(\Lambda)=\phi(0)=0\}, \\ R_4&= \{1\psi \mid \psi(0)=1,\, \psi(00)=0\} \times \{*\phi\mid \phi(\Lambda)=\phi(1)=0\}, \\ R_{11}&= \{0\psi \mid \psi(1)=0,\, \psi(11)=1\} \times \{*\phi\mid \phi(\Lambda)=\phi(0)=1\}, \\ R_{14}&=\{0\psi \mid \psi(1)=1,\, \psi(11)=0\} \times \{*\phi\mid \phi(\Lambda)=\phi(1)=1\}, \\ R_2&= \{*\psi \mid \psi(0)=0,\, \psi(01)=0\} \times\{1\phi \mid \phi(\Lambda)=0,\, \phi(0)=1\}, \\ R_3&= \{*\psi \mid \psi(0)=0,\, \psi(01)=1\} \times\{1\phi \mid \phi(\Lambda)=0,\, \phi(0)=1\}, \\ R_6&= \{*\psi \mid \psi(0)=1,\, \psi(01)=0\} \times\{0\phi \mid \phi(\Lambda)=0,\, \phi(1)=1\}, \\ R_7&= \{*\psi \mid \psi(0)=1,\, \psi(01)=1\} \times\{0\phi \mid \phi(\Lambda)=0,\, \phi(1)=1\}, \\ R_8&= \{*\psi \mid \psi(1)=0,\, \psi(10)=0\} \times\{1\phi \mid \phi(\Lambda)=1,\, \phi(0)=0\}, \\ R_9&= \{*\psi \mid \psi(1)=0,\, \psi(10)=1\} \times\{1\phi \mid \phi(\Lambda)=1,\, \phi(0)=0\}, \\ R_{12}&= \{*\psi \mid \psi(1)=1,\, \psi(11)=0\} \times\{0\phi \mid \phi(\Lambda)=1,\, \phi(1)=0\}, \\ R_{13}&=\{*\psi \mid \psi(1)=1,\, \psi(11)=1\} \times\{0\phi \mid \phi(\Lambda)=1,\, \phi(1)=0\}, \\ S_1&=\{0\psi \mid \psi(0)=0,\, \psi(00)=1\}\times \{\mathtt{r}\}, \\ S_4&=\{0\psi \mid \psi(0)=1,\, \psi(00)=0\}\times\{\mathtt{r}\}, \\ S_{11}&=\{1\psi \mid \psi(1)=0,\, \psi(11)=1\}\times\{\mathtt{r}\}, \\ S_{14}&=\{1\psi \mid \psi(1)=1,\, \psi(11)=0\}\times\{\mathtt{r}\}, \\ S_2&=\{\mathtt{r}\eta \mid \eta(001)=0\}\times\{0\phi \mid \phi(\Lambda)=0,\, \phi(0)=1\}, \\ S_3&=\{\mathtt{r}\eta \mid \eta(001)=1\}\times\{0\phi \mid \phi(\Lambda)=0,\, \phi(0)=1\}, \\ S_6&=\{\mathtt{r}\eta \mid \eta(011)=0\}\times\{1\phi \mid \phi(\Lambda)=0,\, \phi(1)=1\}, \\ S_7&=\{\mathtt{r}\eta \mid \eta(011)=1\}\times\{1\phi \mid \phi(\Lambda)=0,\, \phi(1)=1\}, \\ S_{8}&=\{\mathtt{r}\eta \mid \eta(100)=0\}\times\{0\phi \mid \phi(\Lambda)=1,\, \phi(0)=0\}, \\ S_{9}&=\{\mathtt{r}\eta \mid \eta(100)=1\}\times\{0\phi \mid \phi(\Lambda)=1,\, \phi(0)=0\}, \\ S_{12}&=\{\mathtt{r}\eta \mid \eta(110)=0\}\times\{1\phi \mid \phi(\Lambda)=1,\, \phi(1)=0\}, \\ S_{13}&=\{\mathtt{r}\eta \mid \eta(110)=1\}\times\{1\phi \mid \phi(\Lambda)=1,\, \phi(1)=0\}. \end{aligned}
\end{equation*}
\notag
$$
Lemma 5. (1) All cells of rectangles $R_i$ and $S_i$ contain the integer $i$. (2) If $u$ and $v$ are cells from different fooling rectangles, then the set $\{u,v\}$ cannot be covered by a monochromatic rectangle (in particular, $u\ne v$, that is, fooling rectangles are pairwise disjoint). For the matrix $M$ this can be verified directly by examining Figure 10. For $U$ the proof is presented in § 7.1. We call two fooling rectangles horizontally adjacent if their first projections intersect (there is a row that intersects both rectangles). Consider the nonoriented graph whose nodes are fooling rectangles and whose edges connect horizontally adjacent rectangles. We say that a vertex $u$ is a neighbour of a vertex $v$ if $u$ and $v$ are adjacent. In particular, each node is a neighbour of its own. It turns out that this graph has the following expansion property. The proof of this lemma is deferred to § 7.2. Let us derive from this lemma the proof for horizontal partitions. Assume that rows of the matrix are divided into sets $W$ and $V$. Denote by $\mathcal R$ the set of all fooling rectangles which intersect some row in $W$. If there are at least 17 such rectangles, then we are done. Otherwise there are at least $25-16=9$ rectangles outside $\mathcal R$. For these rectangles every row intersecting a rectangle belongs to $V$. Thus every neighbour $y$ of every vertex $x$ outside $\mathcal R$ intersects a row in $V$. (Indeed, there is a row $s$ intersecting both $x$ and $y$. This row is not in $W$, as otherwise $x$ would be in $\mathcal R$. Hence $s\in V$, and $y$ intersects a row in $V$.) Since there are at least nine rectangles outside $\mathcal R$, the lemma implies that there are at least 17 fooling rectangles intersecting a row in $V$. The case of horizontal partitions is complete. Now we are able to explain how we delete rows from the matrix $U$ to construct $M$. Each row of $U$ yields a clique in the adjacency graph, and the graph is the union of such cliques. We choose a minimal set of cliques whose union covers the graph and delete the remaining rows. 5.2.2. The proof for vertical partitionsWe call two fooling rectangles vertically adjacent if their second projections intersect. Unfortunately, an analogue of Lemma 6 is not true any longer. Indeed, the connected components of the vertical adjacency graph are the following ones:
$$
\begin{equation*}
\begin{gathered} \, \{S_1,S_{4},S_{11},S_{14}\}, \\ \{R_0,S_2,S_{3},S_6,S_{7},R_{1},R_{2},R_{3},R_{4},R_6,R_7\}, \\ \{S_8,S_{9},S_{12},S_{13},R_{8},R_{9},R_{11},R_{12},R_{13},R_{14}\}. \end{gathered}
\end{equation*}
\notag
$$
These components correspond to the three sub-matrices into which the matrix $M$ is divided by ordinary vertical lines in Figure 7. Let us join the first and second connected components. In this way we obtain a vertical partition of the matrix into two sub-matrices, where the first sub-matrix intersects 15 fooling rectangles, and the second intersects ten fooling rectangles. This obstacle forces us to increase the number of fooling rectangles. This can be done by adding rectangles with cells containing 0. To do this we reduce the rectangle $R_0$ and add certain rectangles called $R_5$, $R_{10}$, $R_{15}$ and $S_0$. Namely, let
$$
\begin{equation*}
\begin{aligned} \, R_{abab}&= \{*\psi \mid \psi(a)=\psi(aa)=b,\,\psi(\overline a)\ne\psi(\overline a\overline a)\} \\ &\qquad\times \{\overline b\phi\mid \phi(\Lambda)=\phi(b)=a,\,\phi(\overline b)=\overline a\},\quad\text{where }a,b=0,1, \end{aligned}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
S_{0}=\{\mathtt{r}\eta \mid \eta \text{ is arbitrary}\} \times\{i\phi\mid\phi(\Lambda)=\phi(i)\}.
\end{equation*}
\notag
$$
Here are the explicit definitions of the rectangles $R_{abab}$:
$$
\begin{equation*}
\begin{aligned} \, R_0&= \{*\psi\mid \psi(0)=0,\, \psi(00)=0,\, \psi(1)\ne\psi(11)\} \\ &\qquad\times\{1\phi \mid \phi(\Lambda)=0,\, \phi(0)=0,\, \phi(1)=1\}, \\ R_5&= \{*\psi\mid \psi(0)=1,\, \psi(00)=1,\, \psi(1)\ne\psi(11)\} \\ &\qquad\times\{0\phi \mid \phi(\Lambda)=0,\, \phi(1)=0,\, \phi(0)=1\}, \\ R_{10}&= \{*\psi\mid \psi(1)=0,\, \psi(11)=0,\, \psi(0)\ne\psi(00)\} \\ &\qquad\times\{1\phi \mid \phi(\Lambda)=1,\, \phi(0)=1,\, \phi(1)=0\}, \\ R_{15}&= \{*\psi\mid \psi(1)=1,\, \psi(11)=1,\, \psi(0)\ne\psi(00)\} \\ &\qquad\times\{0\phi \mid \phi(\Lambda)=1,\, \phi(1)=1,\, \phi(0)=0\}. \end{aligned}
\end{equation*}
\notag
$$
In fact, for the matrix $M$ the new version of the rectangle $R_0$ coincides with the old one, since the difference between them is due to those rows that were removed from the matrix $U$. The fooling rectangles for the matrix of $M$ are shown in Figure 11. We need an analogue of the Lemma 5 for new fooling rectangles. Lemma 7. (1) All cells of the rectangles $R_0$, $R_5$, $R_{10}$, $R_{15}$ and $S_0$ contain $0$. (2) No two cells $u$ and $v$ in different rectangles from the list $R_0$, $S_0$, $R_5$, $R_{10}$, $R_{15}$ can be covered by a single monochromatic rectangle (cells of old fooling rectangles are marked with nonzeros, so they can also be added to this list). Figure 11. For $U$ the lemma is proved in § 7.3. To complete the proof of the theorem, we need an analogue of Lemma 6 for the vertical adjacency graph. The number of fooling rectangles has increased to 29, so instead of 9 we now have $29-16=13$. As before, this implies that for any vertical partitioning of the matrices $M$ and $U$ into two parts at least one of these parts contains a fooling set of 17 cells. The case of vertical partitions is complete (modulo Lemmas 7 and 8). § 6. Open questions1. Is there a partial function $f$ on words of length $n$ over a fixed alphabet with a super-logarithmic gap between the local half-duplex and local classical complexities? 2. Is there a total function with values 0 and 1 for which the half-duplex complexity is strictly less than the classical complexity? 3. Is there a total function $f$ on words of length $n$ over a fixed alphabet with a super-constant gap between the half-duplex and classical complexities? We believe that all of our questions have an answer in the affirmative. Regarding the third question, we think that the appropriate example is the $n$th power of the function from § 5 but we do not see any ways to prove this. AcknowledgmentsThe authors are sincerely grateful to Timur Kuptsov and anonymous referees for helpful suggestions. § 7. Appendix: deferred proofs7.1. The proof of Lemma 5 for $U$(1) This is verified directly. Let us perform this verification, say, for the rectangle $R_6=R_{0110}$: in the first round both players send bits that are lost and have no effect on the 2–5-transcript. In the second round Bob sends 0 (because $\phi(\Lambda)=0$). Then Alice sends 1 (since $\psi(0)=1$). Then Bob sends 1 (since $\phi(1)=1$). Finally, in the last round Alice sends 0, since $\psi(01)=0$. We obtain the 2–5-transcript 0110. (2) Let $u$ and $v$ belong to different fooling rectangles. Case 1. These rectangles have different subscripts. Then $U(u)\ne U(v)$ by part (1). Hence $u$ and $v$ cannot be covered by a monochromatic rectangle. Case 2. The rectangles containing $u$ and $v$ have the same subscript. Assume first that $u\in R_{abcd}$ and $v\in S_{abcd}$ where $a\ne c$. Then $u=(*\psi,\overline b\phi)$ and $v=(\mathtt{r}\eta,b\phi')$. Consider the input pair $(\mathtt{r}\eta,\overline b\phi)$. First, the 2–5-transcript for this pair is different from $abcd$. Indeed, since for this input pair in the first round Alice receives $\overline b$ from Bob, she sends $\overline b$, rather than $b$, in the third round. Therefore, the transcript for these inputs is different from $abcd$, and it cannot be identified with $abcd$, because the first and third bits are distinct in the latter. Assume now that $u\in R_{abcd}$ and $v\in S_{abcd}$, where $a=c$ and $b\ne d$. Then $u=(\overline a\psi,*\phi)$ and $v=(a\psi',\mathtt{r})$. Consider the input pair $(\overline a\psi,\mathtt{r})$. We claim that the transcript for these inputs is different from $abcd$. In fact, as Bob receives $\overline a$ from Alice in the first round, he sends $\overline a$ in the second. Hence for these inputs the transcript begins with $\overline a$, and therefore it is different from $abcd$. Moreover, they cannot be identified because $b\ne d$. The lemma is proved. 7.2. Proof of Lemma 6We need an explicit description of edges of the graph. Lemma 9. The graph of horizontally adjacent fooling rectangles is the union of the following graphs (see Figure 12). 1. The complete 4-partite graph whose first part is $\{S_2,S_3\}$, the second part is $\{S_{6},S_{7}\}$, the third is $\{S_{8},S_{9}\}$ and the fourth is $\{S_{12},S_{13}\}$. 2. The complete bipartite graph whose first part is $\{R_0,R_1,S_1\}$ and the second part is $\{R_2,R_3\}$. 3. The complete bipartite graph whose first part is $\{R_4,S_4\}$ and the second part is $\{R_6,R_7\}$. 4. The complete bipartite graph whose first part is $\{R_{11},S_{11}\}$ and the second part is $\{R_8,R_9\}$. 5. The complete bipartite graph whose first part is $\{R_{14},S_{14}\}$ and the second part is $\{R_{12},R_{13}\}$. 6. The complete bipartite graph whose first part is $\{R_0,R_1,R_2,R_3,R_4,R_{6},R_{7},S_1,S_4\}$ and the second part is $\{R_{8}, R_{9}, R_{11}, R_{12}, R_{13}, R_{14}, S_{11}, S_{14}\}$, with the exception of all edges of the complete bipartite graph whose first part is $\{R_1, R_4, S_{11}, S_{14}\}$ and the second part is $\{R_{11},R_{14},S_1,S_4\}$. Proof. Note that for the proof of Lemma 6 we need not show that there are no other edges. We only need to show that all edges listed above are indeed present in the graph. For the matrix $M$ this can be verified by looking at Figure 10. For $U$ this is proved as follows.
Recall that two rectangles are connected by an edge if their first projections intersect. We call the second character of the word from the first projection of a rectangle its $\psi$- or $\eta$-projection. In item 1 we listed all fooling rectangles whose first projections contain words of the form $\mathtt{r}*$. Their first projections have the form $\{\mathtt{r}\eta\mid \eta(bac)=d\}$. Such a set does not intersect another set $\{\mathtt{r}\eta\mid \eta(\widetilde b\widetilde a\widetilde c)=\widetilde d\}$ of this form only if $a=\widetilde a$, $b=\widetilde b$, $c=\widetilde c$ but $d\ne\widetilde d$. That is, in the set of rectangles $S_2$, $S_3$, $S_6$, $S_7$, $S_8$, $S_9$, $S_{12}$, $S_{13}$, only for the pairs $(S_{0010},S_{0011})$, $(S_{0110},S_{0111})$, $(S_{1000},S_{1001})$ and $(S_{1100},S_{1101})$ there are now edges connecting rectangles. The first projections of all other fooling rectangles contain words of the form $*\psi$. Except for the rectangles $R_1$, $R_4$, $R_{11}$, $R_{14}$, $S_1$, $S_4$, $S_{11}$ and $S_{14}$, their first character can be arbitrary. For these exceptional rectangles the first character is 1 for $R_1$, $R_4$, $S_{11}$ and $S_{14}$, and it is 0 for $R_{11}$, $R_{14}$, $S_1$ and $S_4$. This explains the exclusion of edges in the sixth item. It is not difficult to verify that in items 2–5 no edges are excluded for this reason: in these items, there are no rectangles from the list $R_1$, $R_4$, $R_{11}$, $R_{14}$, $S_1$, $S_4$, $S_{11}$, $S_{14}$ in one of the parts. It remains to verify that in items 2–6 the $\psi$- or $\eta$-projections intersect. In items 2–5 edges connect rectangles $R_{abad}$ and $S_{abad}$ with rectangles of the form $R_{ab\overline a*}$. We need to prove that the $\psi$-projections of $R_{abad}$ and $S_{abad}$ intersect with the $\psi$-projection of $R_{ab\overline a*}$. Note that the $\psi$-projections of $R_{abad}$ and $S_{abad}$ coincide and are equal to On the other hand the $\psi$-projection of $R_{ab\overline ae}$ is equal to
$$
\begin{equation*}
C=C_e=\{\psi \mid \psi(a)=b,\, \psi(a\overline a)=e\}.
\end{equation*}
\notag
$$
Therefore, the intersection $A\cap C$ includes all the $\psi$ such that $\psi(a)=b$, $\psi(aa)=d$ and $\psi(a\overline a)=e$ (it is important that these assumptions about $\psi$ are compatible).
In the sixth item the rectangles in the first part have the form $R_{0bcd}$ and $S_{0b0\overline b}$, and in the second part rectangles have the same form, except that 0 and 1 are swapped: $R_{1b'c' d'}$ and $S_{1b'1\overline{b'}}$. Their $\psi$-projections are equal, respectively, to
$$
\begin{equation*}
\begin{gathered} \, \{\psi\mid \psi(0)=b,\,\psi(0c)=d\}, \qquad \{\psi\mid \psi(0)=b,\,\psi(00)=\overline b\}, \\ \{\psi\mid \psi(1)=b',\,\psi(1c')=d'\},\qquad \{\psi\mid \psi(1)=b',\,\psi(11)=\overline{b'}\}. \end{gathered}
\end{equation*}
\notag
$$
Clearly, the first and second sets intersect with the third and fourth.
Lemma 9 is proved. Now we are able to prove Lemma 6 by considering several cases. The following sets of nine vertices have the minimum number of neighbours (17):
Let us show that this is indeed the minimum number. Assume that a set $A$ of vertices contains $k$ vertices from the left-hand connected component and $l$ vertices from the right-hand one, $k+l=9$. Since there are only eight vertices in the right-hand component, we know that $k\geqslant1$. We distinguish two cases: $l=0$ and $l\geqslant1$. The case when $l=0$ and $k\,{=}\,9$. It is not difficult to verify that each vertex $u$ from the left-hand component has at least nine neighbours. So the number of non-neighbours of $u$ in the left-hand component does not exceed $17-9=8$. Therefore, $u$ is a neighbour of any set of nine vertices from the left-hand component. Since this is true for any vertex $u$, every of the 17 nodes in the left-hand component is a neighbour of each set of nine vertices in this component, and we are done. The case when $l\geqslant 1$. First assume that $l\geqslant2$. Then one left-hand vertex in $A$ has nine neighbours or more in the left-hand component, and the two right-hand vertices in $A$ have eight neighbours in the right-hand component (if these vertices are from the same circle, then they are neighbours of themselves, otherwise they are neighbours of each other, and the remaining six vertices are their neighbours since they belong to another part relative to one of these two vertices). In total, we obtain 17 neighbours. Otherwise we have $k=8$ and $l=1$. One right-hand vertex in $A$ has seven neighbours, and it is sufficient to verify that each set $B$ of eight vertices from the left-hand component has at least ten neighbours. Note that there are only four vertices with nine neighbours in the left-hand component, and all the other have at least ten neighbours each. Therefore, $B$ contains a vertex with ten neighbours. Lemma 6 is proved. 7.3. The proof of Lemma 7 for $U$(1) For the rectangles $R_i$ this is verified directly. For the rectangle $S_0$: let the pair $(\mathtt{r}\eta, i\phi)$ belong to $S_0$. Let $j$ denote $\phi(\Lambda)=\phi(i)$. In the first round Alice receives $i$ from Bob. Therefore, Alice sends $i$ in the third round. Thus, the transcript in rounds 2–4 looks like $jij$. Finally, in the fifth round Alice sends $i$ again, since the bits she received in the second and fourth rounds coincide. We obtain the transcript $jiji$, hence we have zero in the cell $(\mathtt{r}\eta,i\phi)$ of the matrix. (2) Let $u$ and $v$ belong to different fooling rectangles. First assume that both rectangles have the form $R_{abab}$. Say, the first has the subscript $abab$, and the second the subscript $a'b'a'b'$. Let $u=(*\psi,\overline b\phi)$ and $v=(*\psi',\overline{b'}\phi')$. Then we know that andConsider the input pair $(*\psi,\overline{b'}\phi')$. We claim that $U(*\psi,\overline{b'}\phi')\ne 0$. For a contradiction assume that the 2–5-transcript for this input pair is a multiple of 5, that is, it has the form $\alpha\beta\alpha\beta$. Then we additionally know that and We claim that it follows from (7.1)–(7.6) that $a=a'=\alpha$ and $b=b'=\beta$, and therefore the rectangles $R_{abab}$ and $R_{a'b'a'b'}$ coincide. From (7.5) and (7.2) it follows that $\alpha\ne\overline a$, that is, $\alpha=a$. On the other hand it follows from (7.3) and (7.6) that $\alpha=\phi'(\Lambda)=a'$. From (7.6) it follows that $\phi'(\beta)=\alpha=a$. Now from (7.4) and (7.6) it follows that $\phi'(\overline{b'})\ne a'=\alpha=\phi'(\beta)$, which means that $\overline{b'}\ne\beta$, that is, $\beta=b'$. Finally, from (7.5) and (7.1) we conclude that $\beta=\psi(\alpha)=\psi(a)=b$.It remains to consider the case when one rectangle is $R_{abab}$, and the other is $S_0$. In this case we have $u=(\mathtt{r}\eta,\mathtt{r})$ and $v=(a'\psi',\overline{b'}\phi')$, and we know equalities (7.3) and (7.4). We want to prove that $U(\mathtt{r}\eta,\overline{b'}\phi')\ne0$. For a contradiction assume that the 2–5-transcript for this input pair has the form $\alpha\beta\alpha\beta$. Then we also know (7.6), and moreover, $\beta=\overline{b'}$, since in the third round Alice sends the bit $\overline{b'}$ received from Bob. From (7.6) we derive that $\alpha=\phi'(\beta)=\phi'(\overline{b'})$. On the other hand it follows from (7.3) and (7.6) that $\alpha=\phi'(\Lambda)=a'$. Therefore, $a'=\phi'(\overline{b'})$, which contradicts (7.4). Lemma 7 is proved. 7.4. The proof of Lemma 8Again, we need a more explicit description of edges of the graph. Lemma 10. The vertical adjacency graph is equal to the graph shown in Figure 13 (for both the matrices $U$ and $M$). Proof. For $M$ this lemma is verified directly by looking at the matrix of the function. For $U$ the proof is as follows. Let us write out the second projections of fooling rectangles:
$$
\begin{equation*}
\begin{aligned} \, \operatorname{pr}_2 R_{ab\overline a d} &= \{\overline b\phi\mid \phi(\Lambda)=a,\,\phi(b)=\overline a\}, \\ \operatorname{pr}_2 R_{aba\overline b}&=\{*\phi\mid \phi(\Lambda)=a,\, \phi(b)=a\}, \\ \operatorname{pr}_2R_{abab}&= \{\overline b\phi\mid \phi(\Lambda)=a,\,\phi(b)=a,\,\phi(\overline b)=\overline a\}, \\ \operatorname{pr}_2S_{ab\overline ad}&=\{b\phi\mid \phi(\Lambda)=a,\,\phi(b)=\overline a\}, \\ \operatorname{pr}_2S_{aba\overline b}&= \{\mathtt{r}\}, \end{aligned}
\end{equation*}
\notag
$$
and To prove the lemma we make several simple observations, immediately following from the definitions.
1. The graph splits into two connected components: $\{S_1, S_4,S_{11},S_{14}\}$ (their second projection contains only $\mathtt{r}$) and all other vertices. The first component is a complete graph on the vertices $\{S_1, S_4,S_{11},S_{14}\}$. 2. The vertex $S_0$ is adjacent to all vertices $R_i$, except $R_0$, $R_5$, $R_{10}$ and $R_{15}$. 3. If we remove the vertex $S_{0}$, then the second component splits further into two connected components. One of these consists of all vertices of the form $R_{0bcd}$ and $S_{0bcd}$, and the other of all vertices of the form $R_{1bcd}$ and $S_{1bcd}$. Below we call them the second and third components. These components are isomorphic: they are obtained from each other by swapping zero and one. Therefore, it is sufficient to describe only the second component. 4. The second projections of the rectangles $R_{ab\overline a0}$ and $R_{ab\overline a1}$ coincide. Therefore these rectangles are adjacent. Moreover, the edges from them lead to the same vertices. The same applies to pairs of the form $S_{ab\overline a0}$ and $S_{ab\overline a1}$. In particular, the second component contains the edges $(R_0,R_1)$, $(R_2,R_3)$, $(S_2,S_3)$, $(R_4,R_5)$, $(R_6,R_7)$ and $(S_6,S_7)$. 5. Finally, the second component contains all the edges of the complete bipartite graph with first part $R_0$, $R_1$, $R_2$, $R_3$, $S_2$, $S_3$ and second part $R_4$, $R_5$, $R_6$, $R_7$, $S_6$, $S_7$, with the exception of the edges $(R_0,R_4)$, $(R_0,R_5)$, $(R_1,R_5)$ and all edges of the complete bipartite graph with first part $R_0$, $R_2$, $R_3$, $S_6$, $S_7$ and second part $R_5$, $R_6$, $R_7$, $S_2$, $S_3$. In the first part we have listed all vertices $R_{abcd}$ with $a=b=0$ from the second component. In the second part the ones with $a=0$ and $b=1$. Let us verify first that the $\phi$-projections of the end vertices of all the edges listed intersect, that is, the corresponding conditions on $\phi$ are compatible. Given two vertices $R(S)_{00cd}$ and $R(S)_{01c'd'}$ from the second component, the requirements for $\phi(\Lambda)$ in the $\phi$-projections for both vertices coincide. And because the second bits in $00cd$ and $01c'd'$ are distinct, the conditions on $\phi(b)$ reduce to a conditio on $\phi(0)$ for the first vertex and on $\phi(1)$ for the second, so that they are compatible. Finally, if the first vertex is $R_{0000}$ or the second is $R_{0101}$ (or both), then there is an additional requirement $\phi(\overline b)=\overline a$. This condition can be incompatible with the condition on $\phi(b)$ for the second vertex. It is not difficult to verify that this occurs only for the pairs $(R_0,R_4)$, $(R_0,R_5)$ and $(R_1,R_5)$ (for this reason these edges have been excluded). It remains to verify that the first symbols of elements of projections can also be the same. For rectangles of the form $R_{aba\overline b}$, the first characters can be arbitrary. For the rectangles $R_0$, $R_2$, $R_3$, $S_6$ and $S_7$ the first symbol is equal to 1, and for $R_5$, $R_6$, $R_7$, $S_2$ and $S_3$ the first symbol is equal to 0. Because of this, edges between rectangles in the first and second lists were excluded. The lemma is proved. The graph in Figure 13 consists of a complete graph on the vertices $S_1$, $S_{11}$, $S_4$ and $S_{14}$ and two isomorphic graphs on 12 vertices, together with the vertex $S_0$ connecting them. In what follows we call these two parts with 12 vertices each the components of the graph. The smallest set of neighbours of a set of 13 vertices is attained, for example, if we take all 12 vertices from the left-hand component and the vertex $R_0$ from the right-hand one, or take arbitrary nine vertices from the left-hand component and the vertices $S_1$, $S_4$, $S_{11}$ and $S_{14}$. Let us prove that there cannot be fewer neighbours. To do this, we need the following auxiliary notion. Let $A$ be an arbitrary set of vertices from one component of the graph. We denote by $\Gamma(A)$ the set of all neighbours of $A$, and by $\Gamma'(A)$ the set of all neighbours but $S_0$, that is, the set of all neighbours in the interior of this component. We let $\Gamma(n)$ denote the minimum cardinality $|\Gamma(A)|$ over all $n$-element sets in the interior of one component. The quantity $\Gamma'(n)$ is defined in a similar way. The values of these functions, found by exhaustive search, are presented in Table 9. In fact, we need the values of these functions only for $n=1,4,6,7,9$. Table 9.The table of values of the functions $\Gamma$ and $\Gamma'$, expressing the expansion properties of the components of the vertical adjacency graph
Let us finish the proof of Lemma 8 under the assumption that Lemma 11 holds. Let the set $A$ consist of 13 vertices of the adjacency graph. We need to prove that $A$ has at least 17 neighbours. We consider two cases. Case 1: the set $A$ contains the vertex $S_0$. First assume that $A$ contains at least one of the vertices $S_1$, $S_4$, $S_{11}$, $S_{14}$. Then there must be at least $13-1-4=8$ vertices in the left-hand and right-hand components combined. Therefore, one of the components must contain at least $8/2=4$ vertices. Thus the number of neighbours of $A$ is not less than $5+\Gamma'(4)+6\geqslant 5+7+6 =18$ (the vertices $S_0$, $S_1$, $S_4$, $S_{11}$ and $S_{14}$ plus all of neighbours in the interior of the component containing four vertices, plus the neighbours of the vertex $S_0$ in the interior of the other component). Otherwise the set $A$ does not contain any of $S_1$, $S_4$, $S_{11}$ and $S_{14}$. Then there must be at least $13-1=12$ vertices in the left- and right-hand components in total. If there are six vertices in both components, then $A$ has at least $1+2\Gamma'(6)\geqslant 1+2\cdot9=19$ neighbours. Otherwise one of the components has at least $12-5=7$ vertices, and the number of neighbours is at least $1+\Gamma'(7)+6\geqslant 1+10+6 =17$ (the vertex $S_0$ plus all its neighbours in the interior of the component containing seven vertices, plus the neighbours of $S_0$ in the interior of the other component). Case 2: $S_0\notin A$. Assume first that $A$ contains at least one of the vertices $S_1$, $S_4$, $S_{11}$ and $S_{14}$. In total, both components have at least $13-4=9$ vertices from $A$. If all these vertices lie in one component, then the total number of neighbours of $A$ is at least $\Gamma(9)+4\geqslant 13+4=17$ (the neighbours of these nine vertices plus the vertices $S_1$, $S_4$, $S_{11}$ and $S_{14}$). If each component has at least one vertex from $A$ and one of these components has at least six vertices from $A$, then the number of neighbours of $A$ is at least $\Gamma(6)+\Gamma'(1)+4\geqslant\Gamma'(6)+\Gamma'(1)+4\geqslant 9+4+4 =17$. Otherwise there are five vertices in one component and four in the other, and the number of neighbours is at least $\Gamma(5)+\Gamma'(4)+4\geqslant \Gamma'(4)+\Gamma'(4)+4\geqslant7+7+4=18$. It remains to consider the case when $S_0,S_1,S_4,S_{11},S_{14}\notin A$. Since there are only 12 vertices in each component, each component must have at least one vertex from $A$. If one of them has at least nine vertices from $A$, then we obtain at least $\Gamma(9)+\Gamma'(1)\geqslant13+4=17$ neighbours. Otherwise, the splitting of the vertices between components is $5+8$ or $6+7$. In both cases the number of neighbours is not less than $\Gamma(5)+\Gamma'(7)\geqslant\Gamma'(4)+\Gamma'(7)\geqslant7+10=17$. Lemma 8 is proved (modulo Lemma 11). Proof of Lemma 11. (a) This can be verified directly by hand.
(b) Assume that there is a set $A$ of four vertices of the right component that has less than seven neighbours inside this component. First assume that $A$ does not contain vertices from the ovals. Then $A=\{R_0,R_1,R_4,R_5\}$, and $A$ has $12\geqslant7$ neighbours in the interior of the component. So $A$ must contain a vertex from one of the ovals and, without loss of generality, another vertex from the same oval (indeed, adding this other vertex to $A$ does not increase the number of neighbours, so it can replace any other vertex in $A$). Identifying symmetric variants, we can consider only two cases: $R_2,R_3\in A$ and $S_2,S_3\in A$. The first case: $R_2,R_3\in A$. These two vertices in combination already have five neighbours, $R_2$, $R_3$, $R_4$, $S_6$ and $S_7$. It is easy to verify that adding any further vertex to $R_2$ and $R_3$ increases the number of neighbours by 2 at least. The second case: $S_2,S_3\in A $. In combination, these two vertices already have six neighbours, namely, $S_2$, $S_3$, $R_4$, $R_5$, $R_6$ and $R_7$. It is easy to see that adding any vertex but $R_5$ to $S_2$ and $S_3$ increases the number of neighbours. Since we need to add two vertices, we obtain a contradiction. (c) To reduce the number of cases we consider the complements. Let us explain this technique in general. We claim that the inequality $\Gamma'(m)\geqslant n$ implies the inequality $\Gamma'(13-n)\geqslant 13-m$. Indeed, assume that $\Gamma'(13-n)< 13-m$. That is, there is a set $A$ of cardinality $13-n$ which has at most $12-m$ neighbours. Then consider the set $B$ consisting of the nonneighbours of $A$, $|B|\geqslant 12-(12-m)=m$. Then all the neighbours of $B$ lie in the complement of $A$, so $|\Gamma'(B)|\leqslant 12-(13-n)=n-1$. Removing $|B|-m$ vertices from $B$ we obtain a set $B'$ of cardinality precisely $m$ such that $|\Gamma'(B')|\leqslant n-1$. This technique is worth applying when $13-n$ is closer to 6 than $m$, because in this case the number of $(13-n)$-element subsets of a component is less than the number of its $m$-element subsets. For example, statement (c) follows from (b), and we do not have to look over all six-element subsets of a component. (d) It suffices to prove the inequality $\Gamma'(3)\geqslant 6$ using this technique. Assume that there is a set $A$ of three vertices of some component that has fewer than six neighbours in the interior of this component. First assume that $A$ contains no vertices from the ovals. After identifying symmetric variants, there are only two such sets, $\{R_0,R_1,R_4\}$ and $\{R_0,R_1,R_5\}$. In the first case all vertices of the components are neighbours, and in the second case all vertices except $R_2$ and $R_3$ are. Now assume that $A$ contains a vertex from an oval. Without loss of generality we can assume that the other vertex from the oval also lies in $A$. After identifying symmetric cases, only two cases must be considered: $A\ni R_2,R_3$ and $A\ni S_2,S_3$. In the first case the vertices $R_2$ and $R_3$ already have five neighbours in total, $R_2$, $R_3$, $R_4$, $S_6$ and $S_7$, so the third vertex of $A$ must be in this list and may not have neighbours out of the list. Using simple search we can see that there are no such vertices. In the second case the vertices $S_2$ and $S_3$ already have six neighbours in total. (e) Using our technique, we can deduce from (a) that $\Gamma'(9)\geqslant 12$. In addition, the vertex $S_0$ is a neighbour of any set of $12-6+1=7$ vertices lying in the interior of one component, since it has six neighbours in the interior of some component. Therefore, for all $n$ starting from $n=7$, we have $\Gamma'(n)=\Gamma(n)+1$. The lemma is proved.
Citation in format AMSBIB
\Bibitem{VerDek25} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|