Authors Alexander Kozachinskiy, Vladimir V. Podolskii,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2020
Multiparty Karchmer–Wigderson Games
and Threshold Circuits
Alexander Kozachinskiy∗ Vladimir Podolskii†
Received July 16, 2020; Revised May 8, 2022; Published June 12, 2022
Abstract. We propose a generalization of the Karchmer–Wigderson communication
games to the multiparty setting. Our generalization turns out to be tightly connected
to circuits consisting of threshold gates. This allows us to obtain new explicit
constructions of such circuits for several functions. In particular, we provide an
explicit (polynomial-time computable) log-depth monotone formula for the Majority
function, consisting only of 3-bit majority gates and variables. This resolves a
conjecture of Cohen et al. (CRYPTO’13).
1 Introduction
Karchmer and Wigderson established a tight connection between circuit depth and communica-
tion complexity [10] (see also [12, Chapter 9]). They showed that for every Boolean function
A conference version of this paper appeared in the Proceedings of the 35th Computational Complexity Conference,
2020 [11].
∗ The work of A. Kozachinskiy was performed at the Steklov International Mathematical Center and supported by
the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-15-2022-265).
† Supported by the HSE University Basic Research Program and by the Ministry of Science and Higher Education
of the Russian Federation (agreement no. 075-15-2022-265).
ACM Classification: F.1.3, F.1.2
AMS Classification: 68Q17, 68Q25
Key words and phrases: Karchmer–Wigderson games, threshold circuits, threshold gates,
majority function
© 2022 Alexander Kozachinskiy and Vladimir Podolskii
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a015
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
𝑓 one can define a communication game whose communication complexity exactly equals the
depth of 𝑓 in the standard De Morgan basis. This discovery turned out to be very influential in
Complexity Theory. A lot of circuit depth lower bounds as well as formula size lower bounds
rely on this discovery [9, 13, 4, 6, 3]. Karchmer–Wigderson games have been used also in
adjacent areas like Proof Complexity (see, e. g., [14]).
Karchmer–Wigderson games represent a deep connection of two-party communication
protocols with De Morgan circuits. Loosely speaking, one party is responsible for ∧-gates
and the other party is responsible for ∨-gates. In this paper, we address the question of what
would be a natural generalization of Karchmer–Wigderson games to the multiparty setting. Is it
possible to obtain in this way a connection with other types of circuits?
We answer positively to this question: we suggest such a generalization and show its
connection to circuits consisting of threshold gates. To motivate our results we first present
applications we get from this new connection.
1.1 Applications to circuits
It is well-known that the Majority function1, MAJ2𝑛+1 , can be computed by a monotone circuit of
depth 𝑂(log 𝑛). This was first proved by Ajtai, Komlós and Szemerédi [1]. More specifically, they
constructed a polynomial-time computable sorting network of depth 𝑂(log 𝑛), now known as
the AKS sorting network. In turn, any sorting network can be easily converted into a monotone
circuit of the same depth, computing the Majority function. Namely, we first replace every
comparator of the network by a pair of an ∧-gate and an ∨-gate, and then notice that the median
output of the network coincides with the Majority function.
The construction of Ajtai, Komlós and Szemerédi is fairly complicated, and has a large
constant before the log 𝑛. Valiant [15] gave a much simpler proof of the existence of a monotone
formula of depth 𝑂(log 𝑛) for the Majority function. He used the probabilistic method, so his
argument does not give an explicit construction of such a formula.
Several authors (see, e. g., [5, 2]) noticed that Valiant’s proof actually gives a formula of depth
𝑂(log 𝑛) for MAJ2𝑛+1 , consisting only of MAJ3 -gates (and, importantly, with no constants). Once
again, this formula is not explicit. On the other hand, the AKS sorting network gives an explicit
formula of depth 𝑂(log 𝑛) for MAJ2𝑛+1 which consists of ∧-gates and ∨-gates. There is no obvious
way to convert it into a formula which consists of MAJ3 -gates and does not use constants2. For
brevity, we will call these formulas MAJ3 -formulas. So there is a natural question—is it possible
to construct a 𝑀𝐴𝐽3 -formula of depth 𝑂(log 𝑛) for MAJ2𝑛+1 , deterministically in polynomial time?
This question was stated as a conjecture by Cohen et al. in [2]. First, they showed that the
answer is positive under some cryptographic assumptions. Second, they constructed (uncondi-
tionally) a polynomial-time computable MAJ3 -formula of depth 𝑂(log 𝑛) which coincides √ with
log 𝑛)
MAJ𝑛 for all inputs in which the fraction of ones is bounded away from 1/2 by 2−Θ( .
1For technical convenience, in this paper we always assume that the Majority function has an odd number of
inputs.
2If we had constants, we could easily express the disjunction and the conjuction by a MAJ3 gate: MAJ3 (𝑥, 𝑦, 0) =
𝑥 ∧ 𝑦, MAJ3 (𝑥, 𝑦, 1) = 𝑥 ∨ 𝑦.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 2
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
We show that the conjecture of Cohen et al. is true (unconditionally).
Theorem 1.1. There exists a polynomial-time computable MAJ3 -formula of depth 𝑂(log 𝑛) for MAJ2𝑛+1 .
We use the AKS sorting network in the proof. In fact, one can use any polynomial-time
computable construction of a monotone circuit of depth 𝑂(log 𝑛) for MAJ2𝑛+1 . We also obtain
the following general result:
Theorem 1.2. If there is a monotone formula (i. e., a formula consisting of ∧-gates and ∨-gates of fan-in 2)
for MAJ2𝑛+1 of size 𝑠, then there is a MAJ3 -formula for MAJ2𝑛+1 of size 𝑂(𝑠 · 𝑛 log2 (3) ) = 𝑂(𝑠 · 𝑛 1.58... ).
The transformation from the last theorem, however, is not efficient. We can make this
transformation polynomial-time computable, provided log2 (3) is replaced by 1/(1 − log3 (2)) ≈
2.71. In turn, we view Theorem 1.2 as a potential approach to obtain super-quadratic lower
bounds on the monotone formula size for MAJ2𝑛+1 . However, this approach requires better than
an 𝑛 2+log2 (3) lower bound on the formula size of MAJ2𝑛+1 in the {MAJ3 } basis. Arguably, this
basis may be easier to analyze than the standard monotone basis. The best known size upper
bounds in the {∧, ∨} basis and the {MAJ3 } basis are, respectively, 𝑂(𝑛 5.3 ) and 𝑂(𝑛 4.29 ) [7]. Both
bounds are due to Valiant’s method (see [7] also for the limitations of Valiant’s method).
We also study a generalization of the conjecture of Cohen et al. to threshold functions. By
THR𝑏𝑎 we denote the following Boolean function:
(
1 𝑥 contains at least 𝑎 ones,
THR𝑏𝑎 : {0, 1} 𝑏 → {0, 1}, THR𝑏𝑎 (𝑥) =
0 otherwise.
For some reasons (to be discussed below) a natural generalization would be a question of whether
𝑘𝑛+1
THR𝑛+1 can be computed by formula of depth 𝑂(log 𝑛) which does not use constants and
consists only of THR2𝑘+1 -gates. We will call such formulas 𝑄 𝑘 -formulas (note that 𝑄 2 -formulas
are MAJ3 -formulas, because THR32 = MAJ3 ). This question was also addressed by Cohen et al.
in [2]. First, they observed that there is a construction of depth 𝑂(𝑛) (and exponential size).
𝑘𝑛+1
Second, they gave an explicit construction of depth 𝑂(log 𝑛), which coincides with THR𝑛+1 for
all inputs in which the fraction of ones is bounded away from 1/𝑘 by Θ(1/ log 𝑛).
p
However, no exact (even non-explicit) construction with sublinear depth or subexponential
size was known. In particular, Valiant’s probabilistic construction does not work for 𝑘 ≥ 3. In
this paper, we improve depth 𝑂(𝑛) to depth 𝑂(log2 𝑛) and size exp (𝑂(𝑛)) to size 𝑛 𝑂(1) for this
problem.
Theorem 1.3. For any constant 𝑘 ≥ 3 there exists a polynomial-time computable 𝑄 𝑘 -circuit of depth
𝑘𝑛+1
𝑂(log2 𝑛) for THR𝑛+1 (that is, this circuit does not use constants and consists only of THR2𝑘+1 -gates).
1.2 Applications to Multiparty Secure Computations
The conjecture stated in [2] was motivated by applications to Secure Multiparty Computations.
The paper [2] establishes an approach to construct efficient multiparty protocols based on
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 3
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
protocols for a small number of players. More specifically, in their framework one starts with a
protocol for a small number of players and a formula 𝐹 computing a certain boolean function.
Then one combines a protocol for a small number of players with itself recursively, where the
recursion mimics the formula 𝐹.
It is shown in [2] that from our result it follows that for any 𝑛 there is an explicit polynomial
size protocol for 𝑛 players secure against a passive adversary that controls any 𝑡 < 𝑛2 players. It
is also implicit in [2] that from Theorem 1.3 for 𝑘 = 3 it follows that for any 𝑛 there is a protocol
of size 2𝑂(log 𝑛) for 𝑛 players secure against an active adversary that controls any 𝑡 < 𝑛3 players.
2
An improvement of the depth of the formula in Theorem 1.3 to 𝑂(log 𝑛) would result in a
polynomial size protocol [2].
1.3 Multiparty Karchmer–Wigderson games
We now introduce our main conceptual contribution – multiparty Karchmer–Wigderson games.
Let us start with an example. Consider the ordinary monotone Karchmer–Wigderson game
for MAJ2𝑛+1 . In this game, Alice receives a string 𝑥 ∈ MAJ−1 2𝑛+1 (0) and Bob receives a string
−1
𝑦 ∈ MAJ2𝑛+1 (1). In other words, the number of ones in 𝑥 is at most 𝑛 and the number of ones in
𝑦 is at least 𝑛 + 1. The goal of Alice and Bob is to find some coordinate 𝑖 such that 𝑥 𝑖 = 0 and
𝑦 𝑖 = 1. Next, imagine that Bob flips each of his input bits. After that, each party has a vector
with at most 𝑛 ones. Now Alice and Bob have to find a coordinate in which both vectors are 0.
There is a natural generalization of this problem to the multiparty setting. Assume that
there are 𝑘 parties, and each receives a Boolean vector of length 𝑘𝑛 + 1 with at most 𝑛 ones. Let
the goal of parties be to find a coordinate in which all 𝑘 input vectors are 0. How many bits of
communication are needed for that?
For 𝑘 = 2 the answer is 𝑂(log 𝑛), because there exists a monotone formula of depth 𝑂(log 𝑛)
for MAJ2𝑛+1 , and hence the monotone Karchmer–Wigderson game for MAJ2𝑛+1 can be solved in
𝑂(log 𝑛) bits of communication. For 𝑘 ≥ 3 we are only aware of a simple 𝑂(log2 𝑛)-bit solution
based on the binary search.
𝑘𝑛+1
Note that in this problem, each party receives a vector on which THR𝑛+1 equals 0. The goal
is to find a common zero. We can consider a similar problem for any function 𝑓 satisfying a
so-called 𝑄 𝑘 -property: any 𝑘 vectors from 𝑓 −1 (0) have a common zero. In the next definition we
define the 𝑄 𝑘 -property formally and also introduce the related 𝑅 𝑘 -property.
Definition 1.4. Let 𝑄 𝑘 be the set of all Boolean functions 𝑓 satisfying the following property:
for all 𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ∈ 𝑓 −1 (0) there is a coordinate 𝑖 such that 𝑥 1𝑖 = 𝑥 2𝑖 = . . . = 𝑥 𝑖𝑘 = 0.
Further, let 𝑅 𝑘 be the set of all Boolean functions 𝑓 satisfying the following property: for all
𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ∈ 𝑓 −1 (0) there is a coordinate 𝑖 such that 𝑥 1𝑖 = 𝑥 2𝑖 = . . . = 𝑥 𝑖𝑘 .
For 𝑓 ∈ 𝑄 𝑘 let the 𝑄 𝑘 -communication game for 𝑓 be the following communication problem.
There are 𝑘 parties, the 𝑗th party receives a Boolean vector 𝑥 𝑗 ∈ 𝑓 −1 (0). The goal of parties is to
find any coordinate 𝑖 such that 𝑥 1𝑖 = 𝑥 2𝑖 = . . . = 𝑥 𝑖𝑘 = 0.
Similarly, we can define 𝑅 𝑘 -communication games for functions from 𝑅 𝑘 . In the 𝑅 𝑘 -communi-
cation games, the objective of parties is slightly different: their goal is to find any coordinate 𝑖
and a bit 𝑏 such that 𝑥 1𝑖 = 𝑥 2𝑖 = . . . = 𝑥 𝑖𝑘 = 𝑏.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 4
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
Note that 𝑅 2 contains all self-dual functions – that is, functions that take opposite values in
the opposite vertices of a Boolean cube. Similarly, monotone self-dual functions belong to 𝑄 2 . It
is easy to see that 𝑅 2 -communication games are equivalent to Karchmer–Wigderson games for
self-dual functions (one party should flip all the input bits). Moreover, 𝑄2 -communication games
are equivalent to monotone Karchmer–Widgerson games for monotone self-dual functions.
In this paper, we consider 𝑅 𝑘 -communication games as a multiparty generalization of
Karchmer–Wigderson games. In turn, 𝑄 𝑘 -communication games are considered as a generaliza-
tion of monotone Karchmer–Wigderson games. To justify this choice, one should relate them to
some type of circuits.
1.4 Connection to threshold gates and the main result
Every function from 𝑄 𝑘 can be lower bounded by a 𝑄 𝑘 -circuit (that is, by a circuit that does not use
constants and consists only of THR2𝑘+1 -gates). More precisely, let us write 𝐶 ≤ 𝑓 for a Boolean
circuit 𝐶 and a Boolean function 𝑓 if for all 𝑥 ∈ 𝑓 −1 (0) we have 𝐶(𝑥) = 0. Then the following
proposition holds:
Proposition 1.5 ([2]). The set 𝑄 𝑘 is equal to the set of all Boolean functions 𝑓 for which there exists a
𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 .
There is a similar characterization of the set 𝑅 𝑘 via so-called 𝑅 𝑘 -circuits. These are circuits
that does not use constants and consist of THR2𝑘+1 -gates and negations that can only be applied
to input variables.
Proposition 1.6. The set 𝑅 𝑘 is equal to the set of all Boolean functions 𝑓 for which there exists an
𝑅 𝑘 -circuit 𝐶 ≤ 𝑓 .
The proof from [2] of Proposition 1.5 with obvious modifications also works for Proposi-
tion 1.6.
Given 𝑓 ∈ 𝑄 𝑘 , what is the minimal depth of a 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 ? We show that this quantity
is equal (up to a constant factor) to the communication complexity of the 𝑄 𝑘 -communication
game for 𝑓 .
Theorem 1.7. Let 𝑘 ≥ 2 be any constant. Then for any 𝑓 ∈ 𝑄 𝑘 the following two quantities are equal up
to a constant factor:
• the communication complexity of the 𝑄 𝑘 -communication game for 𝑓 ;
• the minimal 𝑑 for which there exists a depth-𝑑 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 .
Similar result can be obtained for 𝑅 𝑘 -communication games.
Theorem 1.8. Let 𝑘 ≥ 2 be any constant. Then for any 𝑓 ∈ 𝑅 𝑘 the following two quantities are equal up
to a constant factor:
• the communication complexity of the 𝑅 𝑘 -communication game for 𝑓 ;
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 5
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
• the minimal 𝑑 for which there exists a depth-𝑑 𝑅 𝑘 -circuit 𝐶 ≤ 𝑓 .
The proof of each theorem is divided into two parts:
(a) transformation of a depth-𝑑 𝑄 𝑘 -circuit (and 𝑅 𝑘 -circuit) 𝐶 ≤ 𝑓 into an 𝑂(𝑑)-bit protocol
computing the 𝑄 𝑘 -communication game (𝑅 𝑘 -communication game, resp.) for 𝑓 ;
(b) transformation of a 𝑑-bit protocol computing the 𝑄 𝑘 -communication game (or 𝑅 𝑘 -
communication game) for 𝑓 into a 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 (an 𝑅 𝑘 -circuit 𝐶 ≤ 𝑓 , resp.) of
depth 𝑂(𝑑).
The first part is simple and the main challenge is the second part. In Section 6 we
also formulate refined versions of Theorems 1.7 and 1.8. We refine these theorems in the
following two directions. First, we take into account circuit size and for this we consider
dag-like communication protocols. Second, we show that transformations (a-b) can be done in
polynomial time (under some mild assumptions).
𝑘𝑛+1
We derive our upper bounds on the depth of MAJ2𝑛+1 and THR𝑛+1 (Theorems 1.1 and 1.3)
from Theorem 1.7. We first solve the corresponding 𝑄 𝑘 -communication games with small number
of bits of communication. Namely, for the case of MAJ2𝑛+1 we use the AKS sorting network to
solve the corresponding 𝑄2 -communication game with 𝑂(log 𝑛) bits of communication. For
𝑘𝑛+1
the case of THR𝑛+1 with 𝑘 ≥ 3 we solve the corresponding 𝑄 𝑘 -communication game by a
simple binary search protocol with 𝑂(log2 𝑛) bits of communication. This is where we get depth
𝑂(log 𝑛) for Theorem 1.1 and depth 𝑂(log2 𝑛) for Theorem 1.3. Again, some special measures
should be taken to make the resulting circuits polynomial-time computable and to control their
size3.
1.5 Our techniques: hypotheses games
As we already mentioned, the hard part of our main result is to transform a protocol into a
circuit.
For this, we develop a new language to describe threshold circuits. For every 𝑓 in 𝑄 𝑘 and in
𝑅 𝑘 we introduce the corresponding 𝑄 𝑘 -hypotheses game and 𝑅 𝑘 -hypotheses game, resp., for 𝑓 .
We show that strategies in these games are equivalent to 𝑄 𝑘 -circuits and 𝑅 𝑘 -circuits. It turns
out that strategies are more convenient than circuits to simulate protocols, since strategies and
protocols operate in the same top-bottom manner.
Once we establish the equivalence of circuits and hypotheses games, it remains for us to
transform a communication protocol into a strategy in a hypotheses game. This is an elaborate
construction presented in Propositions 5.3 and 5.8.
Here is how we define these games. Fix 𝑓 : {0, 1} 𝑛 → {0, 1}. There are two players, Nature
and Learner. Before the game starts, Nature privately chooses 𝑧 ∈ 𝑓 −1 (0) which then cannot be
changed. The goal of Learner is to find some 𝑖 ∈ [𝑛] such that 𝑧 𝑖 = 0. The game proceeds in
3We should only care about the size in case of Theorem 1.3, because depth 𝑂(log 𝑛) immediately gives polynomial
size.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 6
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
rounds. At each round, Learner specifies 𝑘 + 1 families ℋ0 , ℋ1 , . . . , ℋ𝑘 ⊆ 𝑓 −1 (0) to Nature. We
understand this as if Learner makes the following 𝑘 + 1 hypotheses about 𝑧:
“𝑧 ∈ ℋ0 ”,
“𝑧 ∈ ℋ1 ”,
..
.
“𝑧 ∈ ℋ𝑘 ”.
Learner loses immediately if less than 𝑘 hypotheses are true, i. e., if the number of 𝑗 ∈
{0, 1, . . . , 𝑘} satisfying 𝑧 ∈ ℋ𝑗 is less than 𝑘. Otherwise, Nature points out to some hypothesis
which is true. In other words, Nature specifies to Learner some 𝑗 ∈ {0, 1, . . . , 𝑘} such that 𝑧 ∈ ℋ𝑗 .
The game then proceeds in the same manner for some finite number of rounds. At the end,
Learner outputs an integer 𝑖 ∈ [𝑛]. We say that Learner wins if 𝑧 𝑖 = 0.
It is not hard to show that Learner has a winning strategy in the 𝑄 𝑘 -hypotheses game for
𝑓 if and only if 𝑓 ∈ 𝑄 𝑘 . It is instructive to give a proof of the “if” part of this claim: if 𝑓 ∈ 𝑄 𝑘 ,
then Learner has a winning strategy in the 𝑄 𝑘 -hypotheses game for 𝑓 . We will denote by 𝒵 the
set of all 𝑧’s that are compatible with Nature’s answers so far. At the beginning, 𝒵 = 𝑓 −1 (0). If
|𝒵| ≥ 𝑘 + 1, Learner takes any distinct 𝑧 1 , 𝑧 2 , . . . , 𝑧 𝑘+1 ∈ 𝒵 and makes the following hypotheses:
“𝑧 ≠ 𝑧 1 ”,
“𝑧 ≠ 𝑧 2 ”,
..
.
“𝑧 ≠ 𝑧 𝑘+1 ”.
At least 𝑘 hypotheses are true, and any Nature’s response strictly reduces the size of 𝒵. When
the size of 𝒵 becomes equal to 𝑘, Learner is ready to give an answer due to the 𝑄 𝑘 -property of 𝑓 .
This strategy requires exponential in 𝑛 number of rounds. This can be easily improved to
𝑂(𝑛) rounds. Indeed, instead of choosing 𝑘 + 1 distinct elements of 𝒵 split 𝒵 into 𝑘 + 1 disjoint
almost equal parts. Then let the 𝑖th hypotheses be “𝑧 is not in the 𝑖th part”. Any Nature’s
response reduces the size of 𝒵 by a constant factor, until the size of 𝒵 is 𝑘.
For 𝑓 ∈ 𝑄 𝑘 we can now ask what is the minimal number of rounds in a Learner’s winning
strategy. The following proposition gives an exact answer:
Proposition 1.9. For any 𝑓 ∈ 𝑄 𝑘 the following holds. Learner has a 𝑑-round winning strategy in the
𝑄 𝑘 -hypotheses game for 𝑓 if and only if there exists a depth-𝑑 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 .
Proposition 1.9 is the core result for our applications. For instance, we prove Theorem 1.1 by
giving an explicit 𝑂(log 𝑛)-round winning strategy of Learner in the 𝑄 2 -hypotheses game for
MAJ2𝑛+1 . Let us now sketch our construction of this strategy argument (a complete proof can
be found in Section 4).
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 7
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
Assume that the Nature’s input vector is 𝑧 ∈ MAJ−1 2𝑛+1 (0). We start by finding two integers
𝑖, 𝑗 ∈ [2𝑛 + 1] such that either 𝑧 𝑖 = 0 or 𝑧 𝑗 = 0. This can be achieved in 𝑂(log 𝑛) rounds. Namely,
we maintain a set 𝑆 ⊆ [2𝑛 + 1] with a property that 𝑧 equals 0 on some coordinate from 𝑆.
Initially, 𝑆 = [2𝑛 + 1]. Until the size of 𝑆 is 2, we split 𝑆 into 3 almost equal parts 𝑆1 , 𝑆2 , 𝑆3 . We
then make the following 3 hypotheses: “𝑧 is 0 on some coordinate from 𝑆1 ∪ 𝑆2 ”, “𝑧 is 0 on some
coordinate from 𝑆1 ∪ 𝑆3 ”, “𝑧 is 0 on some coordinate from 𝑆2 ∪ 𝑆3 ”. At least 2 hypotheses are
true, and any Nature’s response decreases the size of 𝑆 by a factor of 3/2.
Consider a moment when the size of 𝑆 became equal to 2, and assume that 𝑆 = {𝑖, 𝑗}.
Learner knows that either 𝑧 𝑖 = 0 or 𝑧 𝑗 = 0. It is not hard, at the cost of one more round, to
exclude an option that 𝑧 𝑖 = 𝑧 𝑗 = 0. So we may assume from now on, that either 𝑧 𝑖 = 0, 𝑧 𝑗 = 1 or
𝑧 𝑖 = 1, 𝑧 𝑗 = 0. At the final stage of our construction, we take any polynomial-time computable
monotone formula 𝐹 of depth 𝑂(log 𝑛) for MAJ2𝑛+1 (for instance, one that can be obtained from
the AKS sorting network). We start to descend from the output gate of 𝐹 to one of 𝐹’s inputs.
Throughout this process, we maintain the following invariant: if 𝑔 is the current gate, then
either 𝑔(𝑧) = 0 ∧ 𝑧 𝑖 = 0 or 𝑔(¬𝑧) = 1 ∧ 𝑧 𝑗 = 0 (here ¬ denotes the bitwise negation). Now, assume
w.l.o.g. that 𝑔 is an ∧-gate, and let 𝑔 = 𝑔1 ∧ 𝑔2 . Note that among the following 3 statements:
“𝑔1 (𝑧) = 0 ∧ 𝑧 𝑖 = 0 ∧ 𝑧 𝑗 = 1”,
“𝑔1 (𝑧) = 1 ∧ 𝑔2 (𝑧) = 0 ∧ 𝑧 𝑖 = 0 ∧ 𝑧 𝑗 = 1”,
“𝑔1 (¬𝑧) = 𝑔2 (¬𝑧) = 1 ∧ 𝑧 𝑖 = 1 ∧ 𝑧 𝑗 = 0”,
one is true and two are false. We make 3 hypothesis, each calling one of these 3 statements false.
Nature responses by indicating a false statement. If it indicates the third statement, then we
already know that 𝑧 𝑖 = 0. Otherwise, we can either descend to 𝑔1 or to 𝑔2 . Overall, the last stage
of our construction costs at most depth(𝐹) = 𝑂(log 𝑛) rounds. If we reach an input to 𝐹, we
output the index of the corresponding variable.
In 𝑅 𝑘 -hypotheses games, Nature and Learner play in the same way except that now Learner’s
objective is to find some pair (𝑖, 𝑏) ∈ [𝑛] × {0, 1} such that 𝑧 𝑖 = 𝑏. The following analog of
Proposition 1.9 holds:
Proposition 1.10. For any 𝑓 ∈ 𝑅 𝑘 the following holds. Learner has a 𝑑-round winning strategy in the
𝑅 𝑘 -hypotheses game for 𝑓 if and only if there exists a depth-𝑑 𝑅 𝑘 -circuit 𝐶 ≤ 𝑓 .
1.6 Organization of the paper
In Section 2 we give Preliminaries. In Section 3 we formally define 𝑄 𝑘 -hypotheses games
and 𝑅 𝑘 -hypotheses games, and show their equivalence to 𝑄 𝑘 -circuits and 𝑅 𝑘 -circuits, resp. In
Section 4 we establish our results for the Majority function—Theorems 1.1 and 1.2. Then in
Section 5 we obtain Theorems 1.7 and 1.8—that is, we show that 𝑄 𝑘 -communication games are
equivalent to 𝑄 𝑘 -circuits and 𝑄 𝑘 -hypotheses games, and analogously for 𝑅 𝑘 -communication
games.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 8
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
Proposition 5.1
Proposition 3.1
𝑄 𝑘 -circuits 𝑄 𝑘 -hypotheses games 𝑄 𝑘 -communication games
Proposition 5.3
Proposition 5.2
Proposition 3.2
𝑅 𝑘 -circuits 𝑅 𝑘 -hypotheses games 𝑅 𝑘 -communication games
Proposition 5.8
Figure 1: Our equivalence results. An arrow from, say, “𝑄 𝑘 -hypotheses games” to “𝑄 𝑘 -
communications games” references a transformation of strategies in 𝑄 𝑘 -hypotheses games into
protocols for 𝑄 𝑘 -communication games.
More detailed references concerning these equivalences can be found on Figure 1.6.
In Section 5 we also establish a weak version of Theorem 1.3. Namely, we show that there
𝑘𝑛+1
exists a 𝑄 𝑘 -circuit of depth 𝑂(log2 𝑛) for THR𝑛+1 . Unfortunately, results of Section 5 are not
sufficient to make this circuit polynomial-time computable.
To overcome this, in Section 6 we refine Theorems 1.7 and 1.8 in order to take into account
the circuit size and polynomial-time computability (see Theorems 6.1 and 6.5 below). Then in
Section 7 we derive Theorem 1.3 from results of Section 6. Additionally, in Section 7 we provide
another proof for Theorem 1.1, via results of Section 6. We deduce from our argument a direct
elementary proof of Theorem 1.1 in Section 8. Finally, in Section 9 we formulate some open
problems.
2 Preliminaries
Let [𝑛] denote the set {1, 2, . . . , 𝑛} for 𝑛 ∈ ℕ . For a set 𝑊 we denote the set of all subsets of 𝑊
by 2𝑊 . For two sets 𝐴 and 𝐵 by 𝐵 𝐴 we mean the set of all (total) functions from 𝐴 to 𝐵.
We usually use subscripts to denote coordinates of vectors. In turn, we usually use
superscripts to numerate vectors.
We use a standard terminology for Boolean functions, formulas and circuits [8]. By MAJ𝑛 we
denote the majority function on 𝑛 inputs. By THR𝑚 𝑚 𝑚
𝑘 we denote the function THR 𝑘 : {0, 1} →
𝑘
{0, 1} which outputs 1 if and only if the number of 1’s in the input is at least 𝑘.
We denote the size of a circuit 𝐶 by size(𝐶) and the depth by depth(𝐶). By De Morgan
formulas/circuits we mean formulas/circuits consisting of ∧-gates and ∨-gates of fan-in 2 and
also negations that can only be applied to input variables. By monotone formulas/circuits we
mean formulas/circuits consisting of ∧-gates and ∨-gates of fan-in 2.
We also consider the following classes of circuits/formulas. By 𝑄 𝑘 -circuits and 𝑄 𝑘 -formulas
we mean circuits and formulas, resp., that consist of THR2𝑘+1 gates. We also call 𝑄2 -circuits and
𝑄 2 -formulas MAJ3 -circuits and MAJ3 -formulas. Similarly, by 𝑅 𝑘 -circuits and 𝑅 𝑘 -formulas we
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 9
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
mean circuits and formulas, resp., that consist of THR2𝑘+1 gates and also negations that can only
be applied to input variables. We stress that it is not allowed to use constants in 𝑄 𝑘 -circuits and
𝑅 𝑘 -circuits. For all classes of circuits and formulas considered in this paper, we assume that
negations do not contribute to the depth.
We use the notion of deterministic communication protocols in the multiparty number-in-hand
model. Additionally, to capture the circuit size in our results, we consider not only standard
tree-like protocols, but also dag-like protocols. This notion was considered by Sokolov in [14]. We
use a slightly different variant of this notion. We provide all necessary definitions in the next
subsection.
2.1 Dags and dag-like communication protocols
We consider directed acyclic graphs (dags) with possibly more than one directed edge from one
node to another. A terminal node of a dag 𝐺 is a node with no out-going edges. Given a dag 𝐺,
let
• 𝑉(𝐺) denote the set of nodes of 𝐺;
• 𝑇(𝐺) denote the set of terminal nodes of 𝐺.
For 𝑣 ∈ 𝑉(𝐺) let 𝑂𝑢𝑡 𝐺 (𝑣) be the set of all edges of 𝐺 that start at 𝑣. A dag 𝐺 is called 𝑡-ary if
for every non-terminal node 𝑣 of 𝐺 we have |𝑂𝑢𝑡 𝐺 (𝑣)| = 𝑡. An ordered 𝑡-ary dag is a 𝑡-ary
dag 𝐺 equipped with a mapping from the set of edges of 𝐺 to {0, 1, . . . , 𝑡 − 1}. This mapping,
restricted to 𝑂𝑢𝑡 𝐺 (𝑣), must be injective for every 𝑣 ∈ 𝑉(𝐺) \ 𝑇(𝐺). The value of this mapping on
an edge 𝑒 will be called the label of 𝑒. In other words, any 𝑡 edges that start at the same node
must have different labels.
By a path in 𝐺 we mean a sequence of edges h𝑒1 , 𝑒2 , . . . , 𝑒 𝑚 i such that for every 𝑗 ∈ [𝑚 − 1]
edge 𝑒 𝑗 ends in the same node in which 𝑒 𝑗+1 starts. Note that there may be two distinct paths
visiting the same nodes in the same order, because we allow parallel edges.
We say that a node 𝑤 is a descendant of a node 𝑣 if there is a path from 𝑣 to 𝑤. We call 𝑤 a
successor of 𝑣 if there is an edge from 𝑣 to 𝑤. A node 𝑠 is called the starting node if every other
node is a descendant of 𝑠. Note that any dag has at most one starting node (otherwise there will
be a cycle in this dag).
If a dag 𝐺 has the starting node 𝑠, then by the depth of 𝑣 ∈ 𝑉(𝐺) we mean the maximal
length of a path from 𝑠 to 𝑣. The depth of 𝐺 then is the maximal depth of its nodes.
Let 𝒳1 , 𝒳2 , . . . , 𝒳𝑘 , 𝒴 be finite sets.
Definition 2.1. A 𝑘-party dag-like communication protocol 𝜋 with inputs from 𝒳1 × 𝒳2 × . . . 𝒳𝑘
and with outputs from 𝒴 is a tuple h𝐺, 𝑃1 , 𝑃2 , . . . , 𝑃𝑘 , 𝜙1 , 𝜙2 , . . . , 𝜙 𝑘 , 𝑙i, where
• 𝐺 is an ordered 2-ary dag with the starting node 𝑠;
• 𝑃1 , 𝑃2 , . . . , 𝑃𝑘 is a partition of 𝑉(𝐺) \ 𝑇(𝐺) into 𝑘 disjoint subsets;
• 𝜙 𝑖 is a function from 𝑃𝑖 × 𝒳𝑖 to {0, 1};
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 10
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
• 𝑙 is a function from 𝑇(𝐺) to 𝒴.
The depth of 𝜋 (denoted by depth(𝜋)) is the depth of 𝐺. The size of 𝜋 (denoted by size(𝜋)) is
|𝑉(𝐺)|.
The underlying mechanics of the protocol is as follows. Parties descend from 𝑠 to one
of the terminals of 𝐺. If the current node 𝑣 is not a terminal and 𝑣 ∈ 𝑃𝑖 , then at 𝑣 the 𝑖th
party communicates a bit to all the other parties. Namely, the 𝑖th party communicates the bit
𝑏 = 𝜙 𝑖 (𝑣, 𝑥), where 𝑥 ∈ 𝒳𝑖 is the input of the 𝑖th party. Among the two edges starting at 𝑣,
parties take one labeled by 𝑏 and descend to one of the successors of 𝑣 along this edge. Finally,
when parties reach a terminal 𝑡, they output 𝑙(𝑡).
We say that 𝑥 ∈ 𝒳𝑖 is 𝑖-compatible with an edge 𝑒 from 𝑣 to 𝑤 if one of the following two
conditions hold:
• 𝑣 ∉ 𝑃𝑖 ;
• 𝑣 ∈ 𝑃𝑖 and 𝑒 is labeled by 𝜙 𝑖 (𝑣, 𝑥).
We say that 𝑥 ∈ 𝒳𝑖 is 𝑖-compatible with a path 𝑝 = h𝑒1 , 𝑒2 , . . . , 𝑒 𝑚 i of 𝐺 if for every 𝑗 ∈ [𝑚] it
holds that 𝑥 is 𝑖-compatible with 𝑒 𝑗 . Intuitively, this means that the 𝑖th party, having input 𝑥,
communicates along 𝑝 (from those nodes of 𝑝 where this party is the one to communicate).
Finally, we say that 𝑥 ∈ 𝒳𝑖 is 𝑖-compatible with a node 𝑣 ∈ 𝑉(𝐺) if there is a path 𝑝 from 𝑠 to 𝑣
such that 𝑥 is 𝑖-compatible with 𝑝.
We say that an input (𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ) ∈ 𝒳1 × 𝒳2 × . . . 𝒳𝑘 visits a node 𝑣 ∈ 𝑉(𝐺) if there is a
path 𝑝 from 𝑠 to 𝑣 such that for every 𝑖 ∈ [𝑘] it holds that 𝑥 𝑖 is 𝑖-compatible with 𝑝. Note that
there is a unique 𝑡 ∈ 𝑇(𝐺) such that (𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ) visits 𝑡.
To formulate an effective version of Theorem 1.7 and Theorem 1.8, we need the following
definition.
Definition 2.2. The light form of a 𝑘-party dag-like communication protocol
𝜋 = h𝐺, 𝑃1 , 𝑃2 , . . . , 𝑃𝑘 , 𝜙1 , 𝜙2 , . . . , 𝜙 𝑘 , 𝑙i
is the tuple h𝐺, 𝑃1 , 𝑃2 , . . . , 𝑃𝑘 , 𝑙i.
In other words, to obtain the light form of 𝜋 we just forget about 𝜙1 , 𝜙2 , . . . , 𝜙 𝑘 . So the
light form only contains the underlying ordered dag of 𝜋, the partition of non-terminal nodes
between parties and the labels of terminals. On the other hand, in the light form there is no
information at all how parties communicate at non-terminal nodes.
A protocol 𝜋 computes a relation 𝑆 ⊆ 𝒳1 × 𝒳2 × . . . × 𝒳𝑘 × 𝒴 if the following holds. For every
(𝑥 , 𝑥 2 , . . . , 𝑥 𝑘 ) ∈ 𝒳1 × 𝒳2 × . . . × 𝒳𝑘 there exist 𝑦 ∈ 𝒴 and 𝑡 ∈ 𝑇(𝐺) such that (𝑥 1 , . . . , 𝑥 𝑘 ) visits 𝑡,
1
𝑙(𝑡) = 𝑦 and (𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 , 𝑦) ∈ 𝑆.
Using the language of relations, we can formally define 𝑄 𝑘 -communication games and
𝑅 𝑘 -communication games. Given 𝑓 : {0, 1} 𝑛 → {0, 1}, 𝑓 ∈ 𝑄 𝑘 , we define the 𝑄 𝑘 -communication
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 11
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
game for 𝑓 as the following relation:
𝑆 ⊆ 𝑓 −1 (0) × . . . × 𝑓 −1 (0) ×[𝑛],
| {z }
𝑘
n o
𝑆 = (𝑥 1 , . . . , 𝑥 𝑘 , 𝑗) | 𝑥 1𝑗 = . . . = 𝑥 𝑗𝑘 = 0 .
Similarly, given 𝑓 : {0, 1} 𝑛 → {0, 1}, 𝑓 ∈ 𝑅 𝑘 , we define the 𝑅 𝑘 -communication game for 𝑓 as the
following relation:
𝑆 ⊆ 𝑓 −1 (0) × . . . × 𝑓 −1 (0) ×([𝑛] × {0, 1}),
| {z }
𝑘
n o
𝑘
𝑆 = (𝑥 , . . . , 𝑥
1
, (𝑗, 𝑏)) | 𝑥 1𝑗 = . . . = 𝑥 𝑗𝑘 = 𝑏 .
It is easy to see that a dag-like protocol for 𝑆 can be transformed into a tree-like protocol
(i. e., into a protocol whose underlying dag is a tree) of the same depth, but this transformation
can drastically increase the size.
3 Formal treatment of 𝑄 𝑘 -hypotheses and 𝑅 𝑘 -hypotheses games
Fix 𝑓 ∈ 𝑄 𝑘 , 𝑓 : {0, 1} 𝑛 → {0, 1}. Here we define Learner’s strategies in the 𝑄 𝑘 -hypotheses game
for 𝑓 formally. We consider not only tree-like strategies, but also dag-like. To specify a Learner’s
strategy 𝑆 in the 𝑄 𝑘 -hypotheses game for 𝑓 , we have to specify:
• An ordered (𝑘 + 1)-ary dag 𝐺 with the starting node 𝑠;
• a subset ℋ𝑗 (𝑝) ⊆ {0, 1} 𝑛 for every 𝑗 ∈ {0, 1, . . . , 𝑘} and for every path 𝑝 in 𝐺 from 𝑠 to
some node in 𝑉(𝐺) \ 𝑇(𝐺);
• a number 𝑖 𝑡 ∈ [𝑛] for every terminal 𝑡 of 𝐺.
The underlying mechanics of the game is as follows. Let the Nature’s vector be 𝑧 ∈ 𝑓 −1 (0).
Learner and Nature descend from 𝑠 to one of the terminals of 𝐺. More precisely, a position in
the game is determined by a path 𝑝, starting at 𝑠. If the endpoint of 𝑝 is not a terminal, Learner
specifies sets ℋ0 (𝑝), ℋ1 (𝑝), . . . , ℋ𝑘 (𝑝) as its hypotheses. If less than 𝑘 of these sets contain 𝑧,
Nature wins. Otherwise, Nature specifies some 𝑗 ∈ {0, 1, . . . , 𝑘} such that 𝑧 ∈ ℋ𝑗 (𝑝). Among
the 𝑘 + 1 edges that start at the endpoint of 𝑝, the players take one which is labeled by 𝑗. After
that, they extend 𝑝 by this edge. At some point, parties reach a terminal 𝑡 (i. e., the endpoint of
𝑝 becomes equal 𝑡). Then the game ends and Learner outputs 𝑖 𝑡 .
We stress that Learner’s output depends only on 𝑡 but not on a path to 𝑡 (unlike Learner’s
hypotheses). This property will be crucial in establishing a connection between 𝑄 𝑘 -hypotheses
games and 𝑄 𝑘 -circuits.
We now proceed to a formal definition of what it means that 𝑆 is winning for Learner.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 12
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
We say that 𝑧 ∈ 𝑓 −1 (0) is compatible with a path 𝑝 = h𝑒1 , . . . , 𝑒 𝑚 i, starting at 𝑠, if the following
holds. If 𝑝 is of length 0, then every 𝑧 ∈ 𝑓 −1 (0) is compatible with 𝑝. Otherwise, for every
𝑖 ∈ {1, . . . , 𝑚} it should hold that 𝑧 ∈ ℋ𝑗 (h𝑒1 , . . . , 𝑒 𝑖−1 i), where 𝑗 is the label of 𝑒 𝑖 . In other words,
the label of 𝑒 𝑖 should be a possible Nature’s response to Learner’s hypotheses in the position
h𝑒1 , . . . , 𝑒 𝑖−1 i. Informally, this means that Nature, having input 𝑧, can reach a position in the
game which corresponds to a path 𝑝.
We say that a strategy 𝑆 is winning for Learner in the 𝑄 𝑘 -hypotheses game for 𝑓 if for every
path 𝑝, starting at 𝑠, and for every 𝑧 ∈ 𝑓 −1 (0), compatible with 𝑝, the following holds:
• if the endpoint of 𝑝 is not a terminal, then the number of 𝑗 ∈ {0, 1, . . . , 𝑘} such that
𝑧 ∈ ℋ𝑗 (𝑝) is at least 𝑘;
• if the endpoint of 𝑝 is 𝑡 ∈ 𝑇(𝐺), then 𝑧 𝑖𝑡 = 0.
We will formulate a stronger version of Proposition 1.9. For that we need a notion of the light
form of a strategy 𝑆. Namely, the light form of 𝑆 is its ordered dag 𝐺 equipped with a mapping
which to every 𝑡 ∈ 𝑇(𝐺) assigns 𝑖 𝑡 . In other words, the light form contains a “skeleton” of 𝑆 and
Learner’s outputs in terminals (and no information about Learner’s hypotheses).
We can identify the light form of any strategy 𝑆 with a 𝑄 𝑘 -circuit. Namely, put a THR2𝑘+1 -gate
to every non-terminal node 𝑣 of 𝐺, and for every 𝑡 ∈ 𝑇(𝐺) put a variable 𝑥 𝑖𝑡 into 𝑡. Set 𝑠, the
starting node of 𝐺, to be the output gate.
Proposition 3.1. For all Boolean functions 𝑓 ∈ 𝑄 𝑘 the following holds:
(a) if 𝑆 is a Learner’s winning strategy in the 𝑄 𝑘 -hypotheses game for 𝑓 , then its light form, considered
as a 𝑄 𝑘 -circuit 𝐶, satisfies 𝐶 ≤ 𝑓 .
(b) Assume that 𝐶 ≤ 𝑓 is a 𝑄 𝑘 -circuit. Then there exists a Learner’s winning strategy 𝑆 in the
𝑄 𝑘 -hypotheses game for 𝑓 such that the light form of 𝑆 coincides with 𝐶.
In fact, in the paper we only use the item (a) of this proposition. But for completeness, we
also provide a proof of the item (b).
Proof of the item (a) of Proposition 3.1. For a node 𝑣 ∈ 𝑉(𝐺) let 𝑓𝑣 be the function computed by
the circuit 𝐶 at the gate corresponding to 𝑣. We shall prove the following statement. For any
path 𝑝 starting at 𝑠 and for any 𝑧 which is compatible with 𝑝 it holds that 𝑓𝑣 (𝑧) = 0, where
𝑣 is the endpoint of 𝑝. To see why this implies 𝐶 ≤ 𝑓 , take any 𝑧 ∈ 𝑓 −1 (0) and note that 𝑧 is
compatible with the path which starts and ends at 𝑠. The endpoint of this path is 𝑠 and hence
0 = 𝑓𝑠 (𝑧) = 𝐶(𝑧).
We will prove the above statement by backward induction on the length of 𝑝. The longest
path 𝑝 ends in some 𝑡 ∈ 𝑇(𝐺). By definition, 𝑓𝑡 = 𝑥 𝑖𝑡 . On the other hand, since 𝑆 is winning,
𝑧 𝑖𝑡 = 0 for any 𝑧 compatible with 𝑝. In other words, 𝑓𝑡 (𝑧) = 0 for any 𝑧 compatible with 𝑝. The
base is proved.
The induction step is the same if 𝑝 ends in some other terminal. Now assume that 𝑝 ends in
𝑣 ∈ 𝑉(𝐺) \ 𝑇(𝐺). Take any 𝑧 ∈ 𝑓 −1 (0) compatible with 𝑝. Let 𝑝 𝑗 be the extension of 𝑝 by the edge
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 13
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
which starts at 𝑣 and is labeled by 𝑗 ∈ {0, 1, . . . , 𝑘}. Next, let 𝑣 𝑗 be the endpoint of 𝑝 𝑗 (note that
𝑣 0 , 𝑣1 , . . . , 𝑣 𝑘 are successors of 𝑣). Since 𝑆 is winning, the number of 𝑗 ∈ {0, 1, . . . , 𝑘} such that
𝑧 ∈ ℋ𝑗 (𝑝) is at least 𝑘. Hence the number of 𝑗 ∈ {0, 1, . . . , 𝑘} such that 𝑧 is compatible with 𝑝 𝑗 is
at least 𝑘. Finally, by the induction hypothesis this means that the number of 𝑗 ∈ {0, 1, . . . , 𝑘}
such that 𝑓𝑣 𝑗 (𝑧) = 0 is at least 𝑘. On the other hand:
𝑓𝑣 = THR2𝑘+1 ( 𝑓𝑣0 , 𝑓𝑣1 , . . . , 𝑓𝑣 𝑘 ).
Therefore, 𝑓𝑣 (𝑧) = 0, as required.
Proof of the item (b) of Proposition 3.1. The circuit 𝐶 should be the light form of 𝑆. So to define
𝑆, it remains to define hypotheses of Learner in 𝑆. Consider any non-input gate 𝑔 of 𝐶. Let
𝑔0 , . . . 𝑔 𝑘 be gates that are fed to 𝑔, that is, 𝑔 = THR2𝑘+1 (𝑔0 , . . . , 𝑔 𝑘 ). For every path 𝑝 from the
output gate to 𝑔 we define the following hypotheses:
ℋ0 (𝑝) = 𝑔0−1 (0), . . . , ℋ𝑘 (𝑝) = 𝑔 −1
𝑘 (0).
Note that ℋ0 (𝑝), . . . , ℋ𝑘 (𝑝) depend only on the endpoint of 𝑝.
We have to show that this strategy of Learner is winning in the 𝑄 𝑘 -hypotheses game for 𝑓 .
First, let us observe the following: for any path 𝑝 and for any 𝑧 ∈ 𝑓 −1 (0) which is compatible
with 𝑝 it holds that 𝑔(𝑧) = 0, where 𝑔 is the gate at the endpoint of 𝑝. Indeed, if 𝑝 is of length 0,
then 𝑔 is the output gate of 𝐶, and hence 𝑔(𝑧) = 𝐶(𝑧) ≤ 𝑓 (𝑧). Otherwise, note that the game can
come to a gate 𝑔 only if previously Nature indicated that 𝑔(𝑧) = 0.
Now, consider any path 𝑝 and any 𝑧 ∈ 𝑓 −1 (0) which is compatible with 𝑝. We have to show
two things. First, if 𝑝 ends in some non-input gate 𝑔, then the number of 𝑗 ∈ {0, 1, . . . , 𝑘} such
that 𝑧 ∈ ℋ𝑗 (𝑝) is at least 𝑘. Second, if 𝑝 ends in an input variable 𝑥 𝑖 , then 𝑧 𝑖 = 0. The second
claim is already established. As for the first claim, note that if 𝑧 is compatible with 𝑝, then, as
we have proved, 𝑔(𝑧) = THR2𝑘+1 (𝑔0 , . . . , 𝑔 𝑘 )(𝑧) = 0. That is, the number of 𝑗 ∈ {0, 1, . . . , 𝑘} such
that 𝑔 𝑗 (𝑧) = 0 is at least 𝑘, as required.
Similarly, one can define 𝑅 𝑘 -hypotheses games for functions 𝑓 ∈ 𝑅 𝑘 . The only difference this
time is that the goal of Learner is to find an index 𝑖 ∈ [𝑛] and a bit 𝑏 ∈ {0, 1} such that 𝑧 𝑖 = 𝑏.
Correspondingly, the leaves of Learner’s strategies in 𝑅 𝑘 -hypotheses games will be labeled by
pairs from [𝑛] × {0, 1}. When we turn these strategies into circuits, we turn leaves that are
labeled by (𝑖, 0) into 𝑥 𝑖 , and leaves that are labeled by (𝑖, 1) into ¬𝑥 𝑖 .
The same argument as in Proposition 3.1 establishes the following proposition.
Proposition 3.2. For all Boolean functions 𝑓 ∈ 𝑅 𝑘 the following holds:
(a) if 𝑆 is a Learner’s winning strategy in the 𝑅 𝑘 -hypotheses game for 𝑓 , then its light form, considered
as an 𝑅 𝑘 -circuit 𝐶, satisfies 𝐶 ≤ 𝑓 .
(b) Assume that 𝐶 ≤ 𝑓 is an 𝑅 𝑘 -circuit. Then there exists a Learner’s winning strategy 𝑆 in the
𝑅 𝑘 -hypotheses game for 𝑓 such that the light form of 𝑆 coincides with 𝐶.
Remark 3.3. It might be unclear why we prefer to construct strategies instead of constructing
circuits directly, because beside the circuit itself we should also specify Learner’s hypotheses.
The reason is that strategies can be seen as proofs that the circuit we construct is correct.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 14
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
4 Results for Majority
Theorem 4.1 (Restatement of Theorem 1.1). There exists a polynomial-time computable MAJ3 -formula
of depth 𝑂(log 𝑛) for MAJ2𝑛+1 .
Proof. Due to the AKS sorting network [1], there exists an algorithm which in 𝑛 𝑂(1) time produces
a monotone formula 𝐹 of depth 𝑑 = 𝑂(log 𝑛) which computes MAJ2𝑛+1 . Below we will define a
strategy 𝑆𝐹 in the 𝑄2 -hypotheses game for MAJ2𝑛+1 . Strategy 𝑆𝐹 will be winning for Learner.
Moreover, its depth will be 𝑑 + 𝑂(log 𝑛). In the end of the proof, we will refer to Proposition 3.1
to show that 𝑆𝐹 yields a polynomial-time computable MAJ3 -formula of depth 𝑂(log 𝑛) for
MAJ2𝑛+1 .
Strategy 𝑆𝐹 has two phases. The first phase does not use 𝐹 at all, only the second phase
does. The objective of the first phase is to find some distinct 𝑖, 𝑗 ∈ [2𝑛 + 1] such that either
𝑧 𝑖 = 0 ∧ 𝑧 𝑗 = 1 or 𝑧 𝑖 = 1 ∧ 𝑧 𝑗 = 0, where 𝑧 is the Nature’s vector. This can be done as follows.
Lemma 4.2. One can compute in polynomial time a 3-ary tree 𝑇 of depth 𝑂(log 𝑛) with the set 𝑣(𝑇) of
nodes, and a mapping 𝑤 : 𝑣(𝑇) → 2[2𝑛+1] such that the following holds:
• if 𝑟 is the root of 𝑇, then 𝑤(𝑟) = [2𝑛 + 1] ;
• if 𝑣 is not a leaf of 𝑇 and 𝑣 1 , 𝑣2 , 𝑣3 are 3 children of 𝑣, then every element of 𝑤(𝑣) is covered at
least twice by 𝑤(𝑣 1 ), 𝑤(𝑣 2 ), 𝑤(𝑣 3 ) ;
• if 𝑙 is a leaf of 𝑇, then 𝑤(𝑟) is of size 2.
Proof. We start with a trivial tree, consisting only of the root, to which we assign [2𝑛 + 1]. Then
at each iteration we do the following. We have a 3-ary tree in which nodes are assigned to some
subsets of [2𝑛 + 1]. If every leaf is assigned to a set of size 2, we terminate. Otherwise, we pick
any leaf 𝑙 of the current tree which is assigned to a subset 𝐴 ⊆ [2𝑛 + 1] of size at least 3. We
split 𝐴 into 3 disjoint subsets 𝐴1 , 𝐴2 , 𝐴3 of sizes b|𝐴|/3c, b|𝐴|/3c and |𝐴| − 2b|𝐴|/3c. We add 3
children to 𝑙 (which become new leaves) and assign 𝐴1 ∪ 𝐴2 , 𝐴1 ∪ 𝐴3 , 𝐴2 ∪ 𝐴3 to them.
The sizes of 𝐴1 ∪ 𝐴2 , 𝐴1 ∪ 𝐴3 , 𝐴2 ∪ 𝐴3 do not exceed |𝐴| − b|𝐴|/3c ≤ |𝐴| − |𝐴|/3 + 2/3 =
2/3 · (|𝐴| + 1) ≤ 2/3 · (|𝐴| + |𝐴|/3) = 8/9 · |𝐴|. Hence, the size of the set assigned to a node of
depth ℎ is at most (8/9) ℎ · (2𝑛 + 1). This means that at any moment, the depth of the tree is at
most log9/8 (2𝑛 + 1) = 𝑂(log 𝑛). Therefore, we terminate in 3𝑂(log 𝑛) = 𝑛 𝑂(1) iterations, because at
each iteration we add 3 new nodes. Each iteration takes polynomial time.
We use 𝑇 to find 𝑖, 𝑗 ∈ [2𝑛 + 1] such that either 𝑧 𝑖 = 0 or 𝑧 𝑗 = 0. Namely, we descend from
the root of 𝑇 to one of its leaves. Learner maintains an invariant that the leftmost 0-coordinate
of 𝑧 is in 𝑤(𝑣), where 𝑣 is the current node of 𝑇. Let 𝑣 1 , 𝑣2 , 𝑣3 be 3 children of 𝑣. Learner, for
every 𝑖 ∈ [3], makes a hypothesis that the leftmost 0-coordinate of 𝑧 is in 𝑤(𝑣 𝑖 ). Due to the
properties of 𝑤, at least two hypotheses are true. Nature indicates some 𝑣 𝑖 for which this is true,
and Learner descends to 𝑣 𝑖 . When Learner reaches a leaf, it knows a set of size two containing
the leftmost 0-coordinate of 𝑧. Let this set be {𝑖, 𝑗}.
Learner knows that either 𝑧 𝑖 or 𝑧 𝑗 is 0. Thus, (𝑧 𝑖 , 𝑧 𝑗 ) ∈ {(0, 0), (0, 1), (1, 0)}. At the cost of one
round, Learner can ask Nature to identify an element of {(0, 0), (0, 1), (1, 0)} which differs from
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 15
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
(𝑧 𝑖 , 𝑧 𝑗 ). If the pair (1, 0) is identified, then (𝑧 𝑖 , 𝑧 𝑗 ) ∈ {(0, 0), (0, 1)}, and hence 𝑧 𝑖 = 0, i. e., we can
already output 𝑖. In turn, if the pair (0, 1) is identified, we can output 𝑗. Finally, if the pair (0, 0)
is identified, then the objective of the first phase is fulfilled and we can proceed to the second
phase.
The second phase takes at most 𝑑 rounds. In this phase Learner produces a sequence
𝑔0 , 𝑔1 , . . . , 𝑔 𝑑0 , 𝑑0 ≤ 𝑑 of gates of 𝐹 with the following properties. First, the depth of 𝑔 𝑖 is 𝑖.
Second, the last gate 𝑔 𝑑0 is an input variable (i. e., a leaf of 𝐹). Third, each 𝑔 ∈ {𝑔0 , 𝑔1 , . . . , 𝑔 𝑑0 }
satisfies:
𝑔(𝑧) = 0 ∧ (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1) ∨ 𝑔(¬𝑧) = 1 ∧ (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0) .
(4.1)
Here ¬𝑧 denotes the bitwise negation of 𝑧.
At the beginning, Learner sets 𝑔0 = 𝑔out to be the output gate of 𝐹. Let us explain why (4.1)
holds for 𝑔out . Nature’s vector is an element of MAJ−1 2𝑛+1 (0). That is, the number of ones in 𝑧 is at
most 𝑛. In turn, in ¬𝑧 there are at least 𝑛 + 1 ones. Since 𝑔out computes MAJ2𝑛+1 , we have that
𝑔out (𝑧) = 0 and 𝑔out (¬𝑧) = 1. On the other hand, as guaranteed after the first phase, we have
that (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1) ∨ (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0).
Assume now that the second phase is finished, that is, Learner has produced some 𝑔 𝑑0 = 𝑥 𝑘
satisfying (4.1). Then by (4.1) either 𝑔 𝑑0 (𝑧) = 𝑧 𝑘 = 0 or 𝑔 𝑑0 (¬𝑧) = (¬𝑧) 𝑘 = 1. We have 𝑧 𝑘 = 0 in
both cases. Hence, Learner can output 𝑘.
It remains to explain how to fulfill the second phase. It is enough to show the following.
Assume that Learner knows a non-input gate 𝑔 𝑙 of 𝐹 of depth 𝑙 satisfying (4.1). Then in one
round it can either find a gate 𝑔 𝑙+1 of depth 𝑙 + 1 satisfying (4.1) or give a correct answer to the
game.
The gate 𝑔 𝑙+1 will be one of the two gates which are fed to 𝑔 𝑙 . Assume first that 𝑔 𝑙 is an
∧-gate and 𝑔 𝑙 = 𝑢 ∧ 𝑣. From (4.1) we conclude that among the following three statements one is
true and two are false:
𝑢(𝑧) = 0 and (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1), (4.2)
𝑢(𝑧) = 1, 𝑣(𝑧) = 0 and (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1), (4.3)
𝑢(¬𝑧) = 𝑣(¬𝑧) = 1 and (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0). (4.4)
At the cost of one round Learner can ask Nature to indicate one statement which is false for 𝑧.
If Nature says that (4.2) is false for 𝑧, then (4.1) holds for 𝑔 𝑙+1 = 𝑣 (because (4.1) follows from
the disjunction of (4.3) and (4.4)). Next, if Nature says that (4.3) is false for 𝑧, then, by the same
argument, (4.1) holds for 𝑔 𝑙+1 = 𝑢. Finally, if Nature says that (4.4) is false for 𝑧, then we know
that (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1), i. e., Learner can already output 𝑖.
One can deal in the same way with the case when 𝑔 𝑙 is an ∨-gate and 𝑔 𝑙 = 𝑢 ∨ 𝑣. By (4.1)
exactly one of the following three statements is true for 𝑧:
𝑢(𝑧) = 𝑣(𝑧) = 0 and (𝑧 𝑖 , 𝑧 𝑗 ) = (0, 1), (4.5)
𝑢(¬𝑧) = 1 and (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0), (4.6)
𝑢(¬𝑧) = 0, 𝑣(¬𝑧) = 1 and (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0). (4.7)
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 16
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
Similarly, Learner asks Nature to indicate one statement which is false for 𝑧. If Nature says that
(4.5) is false for 𝑧, then (𝑧 𝑖 , 𝑧 𝑗 ) = (1, 0), i. e., Learner can output 𝑗. Next, if Nature says that (4.6)
is false for 𝑧, then (4.1) holds for 𝑔 𝑙+1 = 𝑣. Finally, if Nature says that (4.7) is false for 𝑧, then (4.1)
holds for 𝑔 𝑙+1 = 𝑢.
Thus, 𝑆𝐹 is a winning strategy of depth 𝑂(log 𝑛) of Learner. Apply Proposition 3.1 to 𝑆𝐹 . We
obtain a MAJ3 -formula 𝐹0 ≤ MAJ2𝑛+1 of depth 𝑂(log 𝑛). In fact, 𝐹0 computes MAJ2𝑛+1 . Indeed,
𝐹0 ≤ MAJ2𝑛+1 means that 𝐹0 outputs 0 on every input with at most 𝑛 ones. On the other hand,
𝐹0 consists of MAJ3 gates and hence 𝐹0 computes a self-dual function (that is, it outputs opposite
values in opposite vertices of the Boolean cube). Therefore, 𝐹0 outputs 1 on every input with at
least 𝑛 + 1 ones.
It remains to explain how to compute 𝐹0 in polynomial time. To do so, by Proposition 3.1 it
is sufficient to compute in polynomial time the light form of 𝑆𝐹 , i. e., the underlying tree of 𝑆𝐹
and the outputs of Learner in the leaves It is easy to see that the light form of 𝑆𝐹 is arranged as
follows.
First, compute 𝐹 and compute 𝑇 from Lemma 4.2. For each leaf 𝑙 of 𝑇 do the following. Let
𝑤(𝑙) = {𝑖, 𝑗}. Add 3 children to 𝑙. Two of them will be leaves of 𝑆𝐹 , labeled by 𝑖 and 𝑗. We then
attach a tree of 𝐹 to the remaining child of 𝑙. Then we add to every non-leaf node of 𝐹 one more
child so that now the tree of 𝐹 is 3-ary. Each added child is a leaf of 𝑆𝐹 . If a child was added
to an ∧-gate, then Learner outputs 𝑖 in this child. In turn, if a child was added to an ∨-gate,
then Learner outputs 𝑗 in it. Finally, there are leaves that were in 𝐹 initially, each labeled by
some input variable. In these nodes, Learner outputs the index of the corresponding input
variable.
Theorem 4.3 (Restatement of Theorem 1.2). If there is a monotone formula for MAJ2𝑛+1 of size 𝑠,
then there is a MAJ3 -formula for MAJ2𝑛+1 of size 𝑂(𝑠 · 𝑛 log2 (3) ) = 𝑂(𝑠 · 𝑛 1.58... ).
Proof. Take any monotone formula 𝐹 for MAJ2𝑛+1 whose size is 𝑠, and consider the corresponding
Learner’s strategy 𝑆𝐹 defined in the previous proof. Recall that 𝑆𝐹 has two phases. The goal of
the first phase is to find some 𝑖, 𝑗 ∈ [2𝑛 + 1] such that either 𝑧 𝑖 = 0 ∧ 𝑧 𝑗 = 1 or 𝑧 𝑖 = 1 ∧ 𝑧 𝑗 = 0. To
show the theorem, it is sufficient to accomplish the first phase in log2 𝑛 + 𝑂(1) rounds. Indeed,
then the tree of 𝑆𝐹 is a ternary tree of depth log2 𝑛 + 𝑂(1) with trees of the same size as formula
𝐹 attached to leaves. Overall, its size is 𝑂(3log2 (𝑛)+𝑂(1) · 𝑠) = 𝑂(𝑛 log2 (3) · 𝑠).
A difference from the previous proof is that this time we do not care about explicitness. In
the explicit construction from the previous proof we fulfil the first phase in log3/2 (𝑛) + 𝑂(1)
rounds (in fact, we only bounded it from above by log9/8 (𝑛) + 𝑂(1), to avoid technical details).
To improve it, we need the following lemma, which will be proved by the probabilistic method.
Lemma 4.4. There exists a formula 𝐷 with the following properties:
• formula 𝐷 is a complete ternary tree of depth dlog2 (𝑛)e + 10;
• every non-leaf node of 𝐷 contains a MAJ3 -gate and every leaf of 𝐷 contains a conjunction of 2
variables;
• 𝐷(𝑥) = 0 for every 𝑥 ∈ {0, 1}2𝑛+1 with at most 𝑛 ones.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 17
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
Let us at first explain how to use formula 𝐷 from Lemma 4.4 to accomplish the first phase in
log2 𝑛 + 𝑂(1) rounds. First, as explained in the previous proof, it is sufficient to find two indices
𝑖, 𝑗 ∈ [2𝑛 + 1] such that either 𝑧 𝑖 = 0 or 𝑧 𝑗 = 0. To do so Learner, descends from the output gate
of 𝐷 to some of its leaves. It maintains an invariant that for its current gate 𝑔 of 𝐷 it holds that
𝑔(𝑧) = 0. For the output gate, the invariant is true because by Lemma 4.4 𝐷 is 0 on all Nature’s
possible vectors. If we reached a leaf so that 𝑔 is a conjuction of two variables 𝑧 𝑖 and 𝑧 𝑗 , then the
first phase is fulfilled (by the invariant, 𝑧 𝑖 ∧ 𝑧 𝑗 = 0). Finally, if 𝑔 is a non-leaf node of 𝐷, i. e., a
MAJ3 -gate, then in one round we can descend to one of the children of 𝑔, without violating the
invariant. Indeed, since 𝑔(𝑧) = 0, the same is true for at least 2 children of 𝑔. For each child 𝑔 𝑖 of
𝑔 Learner makes a hypothesis that 𝑔 𝑖 (𝑧) = 0. Any Nature’s response allows us to replace 𝑔 by
some 𝑔 𝑖 .
Proof of Lemma 4.4. Independently for each leaf 𝑙 of 𝐷 choose (𝑖, 𝑗) ∈ [2𝑛 + 1]2 uniformly at
random and put the conjuction 𝑧 𝑖 ∧𝑧 𝑗 into 𝑙. It is enough to demonstrate that for any 𝑥 ∈ {0, 1}2𝑛+1
with at most 𝑛 ones it holds that Pr[𝐷(𝑥) = 1] < 2−2𝑛−1 .
To do so, we use a modification of a standard Valiant’s argument. For any fixed 𝑥 with at
most 𝑛 ones, let 𝑝 be the probability that a leaf 𝑙 of 𝐷 equals 1 on 𝑥. This probability is the same
for all leaves and it does not exceed 1/4. Now, observe that:
Pr[𝐷(𝑥) = 1] = 𝑓 ( 𝑓 ( 𝑓 (. . . 𝑓 (𝑝))) . . .),
| {z }
dlog2 (𝑛)e + 10
where 𝑓 (𝑡) = 𝑡 3 + 3𝑡 2 (1 − 𝑡) = 3𝑡 2 − 2𝑡 3 . Since, 3 𝑓 (𝑡) ≤ (3𝑡)2 , we have:
dlog2 (𝑛)e+10
3 Pr[𝐷(𝑥) = 1] ≤ (3𝑝)2 ≤ (3/4)1000𝑛 < (1/2)−2𝑛−1 .
5 Proof of the Main Theorem
Theorem 1.7 follows from Proposition 5.1 (Subsection 5.1) and Proposition 5.3 (Subsection 5.2).
In turn, Theorem 1.8 follows from Proposition 5.2 (Subsection 5.1) and Proposition 5.8 (Subsec-
tion 5.2).
5.1 From circuits to protocols
Proposition 5.1. For any constant 𝑘 ≥ 2 the following holds. Assume that 𝑓 ∈ 𝑄 𝑘 and 𝐶 ≤ 𝑓 is
a 𝑄 𝑘 -circuit. Then there is a protocol 𝜋, computing the 𝑄 𝑘 -communication game for 𝑓 , such that
depth(𝜋) = 𝑂(depth(𝐶)).
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 18
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
Proof. Let the inputs of parties be 𝑧 1 , . . . , 𝑧 𝑘 ∈ 𝑓 −1 (0). Parties descend from the output gate
of 𝐶 to one of the inputs. They maintain an invariant that for the current gate 𝑔 of 𝐶 it holds
that 𝑔(𝑧 1 ) = 𝑔(𝑧 2 ) = . . . = 𝑔(𝑧 𝑘 ) = 0. If 𝑔 is not yet an input, then 𝑔 = THR2𝑘+1 (𝑔0 , . . . , 𝑔 𝑘 )
for some gates 𝑔0 , . . . , 𝑔 𝑘 . We have for each 𝑧 𝑖 that 𝑔(𝑧 𝑖 ) = THR2𝑘+1 (𝑔0 (𝑧 𝑖 ), . . . , 𝑔 𝑘 (𝑧 𝑖 )) = 0.
Hence for each 𝑧 𝑖 there is at most one gate out of 𝑔0 , . . . , 𝑔 𝑘 satisfying 𝑔 𝑗 (𝑧 𝑖 ) = 1. This means
that in 𝑂(1) bits of communication parties can agree on the index 𝑗 ∈ {0, 1, . . . , 𝑘} satisfying
𝑔 𝑗 (𝑧 1 ) = 𝑔 𝑗 (𝑧 2 ) = . . . = 𝑔 𝑗 (𝑧 𝑘 ) = 0.
Thus, in 𝑂(depth(𝜋)) bits of communication they reach some input of 𝐶. If this input
contains a variable 𝑥 𝑙 , then by the invariant we have 𝑧 1𝑙 = 𝑧 2𝑙 = . . . = 𝑧 𝑙𝑘 = 0, as required.
The same argument can be used to show the following proposition.
Proposition 5.2. For any constant 𝑘 ≥ 2 the following holds. Assume that 𝑓 ∈ 𝑅 𝑘 and 𝐶 ≤ 𝑓 is
an 𝑅 𝑘 -circuit. Then there is a protocol 𝜋, computing the 𝑅 𝑘 -communication game for 𝑓 , such that
depth(𝜋) = 𝑂(depth(𝐶)).
5.2 From protocols to circuits
Proposition 5.3. For every constant 𝑘 ≥ 2 the following holds. Let 𝑓 ∈ 𝑄 𝑘 . Assume that 𝜋 is a
communication protocol computing the 𝑄 𝑘 -communication game for 𝑓 . Then there is a 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓
such that depth(𝐶) = 𝑂(depth(𝜋)).
Proof. Set 𝑑 = depth(𝜋). By Proposition 3.1, it is enough to give an 𝑂(𝑑)-round winning strategy
of Learner in the 𝑄 𝑘 -hypotheses game for 𝑓 .
We will use the following terminology. First, consider any subset 𝒵 ⊆ 𝑓 −1 (0), any set
𝐶 and any function 𝑔 : 𝒵 → 𝐶. Then the 𝑔-value of a tuple (𝑧 1 , . . . , 𝑧 𝑘 ) ∈ 𝒵 𝑘 is a vector
(𝑔(𝑧 1 ), . . . , 𝑔(𝑧 𝑘 )) ∈ 𝐶 𝑘 .
Let 𝑉 be the set of all nodes of the protocol 𝜋 and let 𝑇 be the set of all terminals of the
protocol 𝜋. Consider any set 𝑈 ⊆ 𝑉 and any set 𝒵 ⊆ 𝑓 −1 (0). The following definition is crucial
for our argument.
Definition 5.4. We say that 𝑈 is complete for 𝒵 if there exist a set 𝐶 of size 𝑘 and a function
𝑔 : 𝒵 → 𝐶 with the following property: for every vector 𝑐¯ ∈ 𝐶 𝑘 there exists a node 𝑢 ∈ 𝑈 such
that all tuples from 𝒵 𝑘 whose 𝑔-value is 𝑐¯ visit 𝑢 in the protocol 𝜋. We also say that such 𝑔
establishes completeness of 𝑈 for 𝒵.
In other words, 𝑈 is complete for 𝒵 if there is a way of partitioning 𝒵 into at most 𝑘 parts
such that the following holds. Assume that somebody takes a tuple (𝑧 1 , . . . , 𝑧 𝑘 ) ∈ 𝒵 𝑘 and for
every 𝑖 ∈ [𝑘] tells us the part of 𝒵 to which 𝑧 𝑖 belongs. Then we can determine a node 𝑢 ∈ 𝑈
such that the tuple (𝑧 1 , . . . , 𝑧 𝑘 ) visits 𝑢 in the protocol 𝜋.
We now describe the Learner’s strategy. It proceeds in 𝑑 iterations, each iteration takes 𝑂(1)
rounds of the 𝑄 𝑘 -hypotheses game. Now, we say that a set of nodes 𝑈 ⊆ 𝑉 is ℎ-low if all nodes
of 𝑈 that are not terminals are of depth at least ℎ. Learner maintains the following invariant.
Invariant 5.5. After ℎ iterations, there exists an ℎ-low set of nodes 𝑈 which is complete for the
set 𝒵ℎ of all 𝑧 ∈ 𝑓 −1 (0) that are compatible with Nature’s responses after ℎ iterations.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 19
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
Let us first explain why this invariant holds in the beginning. We need to establish a 0-low
set 𝑈 which is complete for 𝑓 −1 (0). We can take 𝑈 = {𝑠}, where 𝑠 is the starting node of 𝜋. This
is because every tuple visits 𝑠 in the protocol 𝜋.
Next, let us explain that if Invariant 5.5 holds after 𝑑 iterations, then Learner is able to
produce a correct answer to the 𝑄 𝑘 -hypotheses game for 𝑓 . Indeed, there exists a 𝑑-low set
of nodes 𝑈 which is complete for 𝒵𝑑 . Note that 𝑈 consists only of terminals. Therefore, it is
sufficient to establish the following lemma.
Lemma 5.6. Assume that 𝑈 ⊆ 𝑇 is complete for 𝒵 ⊆ 𝑓 −1 (0). Then there exists 𝑖 ∈ [𝑛] such that 𝑧 𝑖 = 0
for every 𝑧 ∈ 𝒵.
Proof. If 𝒵 is empty, then there is nothing to prove. Otherwise, take 𝑔 : 𝒵 → 𝐶, |𝐶 | = 𝑘 which
establishes completeness of 𝑈 for 𝒵. Consider any vector 𝑐¯ = (𝑐1 , . . . , 𝑐 𝑘 ) ∈ 𝐶 𝑘 such that
{𝑐 𝑖 | 𝑖 ∈ [𝑘]} = 𝑔(𝒵). There exists a node 𝑢 ∈ 𝑈 such that any tuple from 𝒵 𝑘 whose 𝑔-value is 𝑐¯
visits 𝑢. Note that 𝑢 is a terminal of 𝜋. Let 𝑖 ∈ [𝑛] be the output of 𝜋 in 𝑢. We show that for
any 𝑧 ∈ 𝒵 it holds that 𝑧 𝑖 = 0. Indeed, note that there exists a tuple 𝑧¯ ∈ 𝒵 𝑘 whose 𝑔-value is
𝑐¯ and which includes 𝑧. This tuple visits 𝑢. Since 𝜋 computes the 𝑄 𝑘 -communication game
for 𝑓 , every element of the tuple 𝑧¯ should have 0 at the 𝑖th coordinate. In particular, this holds
for 𝑧.
Finally, we describe how to maintain Invariant 5.5. Assume that it holds after ℎ iterations.
Let us show how to perform the next iteration to maintain the invariant. We need a notion of a
communication profile for that.
The communication profile of 𝑧 ∈ 𝑓 −1 (0) with respect to a set of nodes 𝑈 ⊆ 𝑉 is a function
𝑝 𝑧 : 𝑈 → {0, 1}, defined as follows. Take any 𝑣 ∈ 𝑈. If 𝑣 is a terminal, set 𝑝 𝑧 (𝑣) = 0. Otherwise,
let 𝑖 ∈ [𝑘] be the index of the party communicating at 𝑣. Set 𝑝 𝑧 (𝑣) to be the bit transmitted by
the 𝑖th party at 𝑣 on input 𝑧. In the words, the communication profile of 𝑧 w.r.t. 𝑈 stores how
all the parties communicate at nodes of 𝑈 on input 𝑧.
We also define the communication profile of a tuple (𝑧 1 , . . . , 𝑧 𝑘 ) ∈ ( 𝑓 −1 (0)) 𝑘 as (𝑝 𝑧 1 , . . . , 𝑝 𝑧 𝑘 ).
Lemma 5.7. Let (𝑧 1 , . . . , 𝑧 𝑘 ), (𝑦 1 , . . . , 𝑦 𝑘 ) ∈ ( 𝑓 −1 (0)) 𝑘 be two inputs visiting the same node 𝑣 ∈ 𝑉 \ 𝑇.
Assume that their communication profiles with respect to {𝑣} coincide. Then these two inputs visit the
same successor of 𝑣.
Proof. Let their common communication profile with respect to {𝑣} be (𝑝 1 , . . . , 𝑝 𝑘 ). Next, assume
that 𝑖 is the index of the party communicating at 𝑣. Then where these inputs descend from 𝑣 is
determined by 𝑝 𝑖 .
Here is what Learner does during the (ℎ + 1)st iteration. It takes any ℎ-low 𝑈 which is
complete for 𝒵ℎ . Then it takes any 𝑔 : 𝒵ℎ → 𝐶, |𝐶| = 𝑘 which establishes completeness of 𝑈 for
𝒵ℎ . Note that w.l.o.g. 𝑈 is of size at most 𝑘 𝑘 . This is because for any vector 𝑐¯ ∈ 𝐶 𝑘 we need
exactly one node in 𝑈 for 𝑐¯ to establish completeness.
Learner now devises a new function 𝑔 0 whose domain is the set 𝒵ℎ . The value of 𝑔 0(𝑧) is a
pair (𝑝 𝑧 , 𝑔(𝑧)), where 𝑝 𝑧 is a communication profile of 𝑧 with respect to 𝑈. There are at most
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 20
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
𝑘
2|𝑈 | ≤ 2 𝑘 different communication profiles with respect to 𝑈. Hence, the image of 𝑔 0 is of size
𝑘
at most 2 𝑘 · 𝑘 = 𝑂(1).
The goal of the (ℎ + 1)st iteration is to narrow down the image of 𝑔 0 to a set of size 𝑘.
Learner does this as follows. While there exist 𝑘 + 1 different possible values of 𝑔 0, Learner
asks Nature to reject one of them. More specifically, for each of these 𝑘 + 1 values, Learner
make a hypothesis that 𝑔 0(𝑧) differs from this value. As the size of the image of 𝑔 0 in the
beginning is 𝑂(1), this process takes 𝑂(1) rounds of the 𝑄 𝑘 -hypotheses game. In the end of the
(ℎ + 1)st iteration, we are left with 𝑘 possible values of 𝑔 0. Denote them by (𝑝 1 , 𝑐1 ), . . . (𝑝 𝑘 , 𝑐 𝑘 ).
In other words, we know that 𝑔 0(𝑍 ℎ+1 ) ⊆ {(𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 )} (recall that 𝑍 ℎ+1 is the set of
𝑧 ∈ 𝑓 −1 (0) that are compatible with the Nature’s responses after ℎ + 1 iterations). We show
that 𝑔 0 : 𝒵ℎ+1 → {(𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 )} = 𝐶 0 establishes completeness of some (ℎ + 1)-low set of
nodes 𝑈 0 for 𝒵ℎ+1 . This will establish Invariant 5.5 after the (ℎ + 1)st iteration.
Take any vector 𝑐¯ ∈ (𝐶 0) 𝑘 . It is enough to show that all the inputs from (𝒵ℎ+1 ) 𝑘 whose
𝑔 -value is 𝑐¯ visit the same node 𝑣 0 which is either a terminal or of depth at least ℎ + 1. Then we
0
just set 𝑈 0 to be the union of all such 𝑣 0 over all 𝑐¯ ∈ (𝐶 0) 𝑘 .
All tuples from (𝒵ℎ+1 ) 𝑘 with the same 𝑔 0-value visit the same node 𝑣 ∈ 𝑈. This is because
𝑔 -value of a tuple determines its 𝑔-value, and hence we can use Invariant 5.5 for 𝒵ℎ here. If 𝑣 is
0
a terminal, there is nothing left to prove. Otherwise, note that 𝑔 0-value of a tuple also determines
its communication profile with respect to 𝑈, and hence with respect to {𝑣} ⊆ 𝑈. Therefore, by
Lemma 5.7, all tuples with this 𝑔 0-value visit the same successor of 𝑣.
With straightforward modifications, one can obtain a proof of the following:
Proposition 5.8. For every constant 𝑘 ≥ 2 the following holds. Let 𝑓 ∈ 𝑅 𝑘 . Assume that 𝜋 is a
communication protocol computing the 𝑅 𝑘 -communication game for 𝑓 . Then there is an 𝑅 𝑘 -circuit
𝐶 ≤ 𝑓 such that depth(𝐶) = 𝑂(depth(𝜋)).
Corollary 5.9 (Weak version of Theorem 1.3). For any constant 𝑘 ≥ 2 there exists a 𝑄 𝑘 -formula of
𝑘𝑛+1
depth 𝑂(log2 𝑛) for THR𝑛+1 .
Proof. We will show that there exists a protocol 𝜋 of depth 𝑂(log2 𝑛) computing the 𝑄 𝑘 -
𝑘𝑛+1
communication game for THR𝑛+1 . By Proposition 5.3 this means that there is a 𝑄 𝑘 -formula
𝑘𝑛+1
𝐹 ≤ THR𝑛+1 of depth 𝑂(log 𝑛). 2
𝑘𝑛+1
It is easy to see that 𝐹 actually coincides with THR𝑛+1 . Indeed, assume for contradiction that
𝐹(𝑥) = 0 for some 𝑥 with at least 𝑛 + 1 ones. Then it is easy to construct 𝑥 2 , . . . , 𝑥 𝑘 , each with 𝑛
ones, such that 𝑥, 𝑥 2 , . . . , 𝑥 𝑘 have no common 0-coordinate. Since 𝐹(𝑥) = 𝐹(𝑥 2 ) = . . . = 𝐹(𝑥 𝑘 ) = 0,
we conclude that 𝐹 does not have the 𝑄 𝑘 -property. But 𝐹 is a 𝑄 𝑘 -formula, so it gives a
contradiction with Proposition 1.5.
Let 𝜋 be the following protocol. Assume that the inputs to parties are 𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ∈
{0, 1} 𝑘𝑛+1 . Without loss of generality, we may assume that each 𝑥 𝑟 has exactly 𝑛 ones. For
𝑥 ∈ {0, 1} 𝑘𝑛+1 define supp(𝑥) = {𝑖 ∈ [𝑘𝑛 + 1] | 𝑥 𝑖 = 1}. Let 𝑇 be a binary rooted tree of depth
𝑑 = log2 (𝑛) + 𝑂(1) with 𝑘𝑛 + 1 leaves. Identify leaves of 𝑇 with elements of [𝑘𝑛 + 1]. For a node
𝑣 of 𝑇, let 𝑇𝑣 be the set of all leaves of 𝑇 that are descendants of 𝑣. Once again, we view 𝑇𝑣 as a
subset of [𝑘𝑛 + 1].
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 21
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
The protocol proceeds in at most 𝑑 iterations. After 𝑖 iterations, for 𝑖 = 0, . . . 𝑑, parties agree
on a node 𝑣 of 𝑇 of depth 𝑖, satisfying the following invariant:
𝑘
Õ
|supp(𝑥 𝑟 ) ∩ 𝑇𝑣 | < |𝑇𝑣 |. (5.1)
𝑟=1
At the beginning, Invariant (5.1) holds just because 𝑣 is the root, 𝑇𝑣 = [𝑘𝑛 + 1] and each supp(𝑥 𝑟 )
is of size 𝑛.
After 𝑑 iterations, 𝑣 = 𝑙 is a leaf of 𝑇. Parties output 𝑙. This is correct because by (5.1) we
have |𝑇𝑙 | = 1 =⇒ |supp(𝑥 𝑟 ) ∩ 𝑇𝑙 | = 0 =⇒ 𝑥 𝑙𝑟 = 0 for every 𝑟 ∈ [𝑘].
Let us now explain what parties do at each iteration. If the current 𝑣 is not a leaf, let 𝑣 0 , 𝑣1
be two children of 𝑣. Each party sends |supp(𝑥 𝑟 ) ∩ 𝑇𝑣0 | and |supp(𝑥 𝑟 ) ∩ 𝑇𝑣1 |, using 𝑂(log 𝑛) bits.
Since 𝑇𝑣0 and 𝑇𝑣1 is a partition of 𝑇𝑣 , we have:
Õ 𝑘
1 Õ 𝑘
Õ 1
Õ
supp(𝑥 𝑟 ) ∩ 𝑇𝑣𝑏 = |supp(𝑥 𝑟 ) ∩ 𝑇𝑣 | < |𝑇𝑣 | = |𝑇𝑣𝑏 |.
𝑏=0 𝑟=1 𝑟=1 𝑏=0
Thus the inequality:
𝑘
Õ
supp(𝑥 𝑟 ) ∩ 𝑇𝑣𝑏 < |𝑇𝑣𝑏 | (5.2)
𝑟=1
is true either for 𝑏 = 0 or for 𝑏 = 1. Let 𝑏 ∗ be the smallest 𝑏 ∈ {0, 1} for which (5.2) is true. Parties
replace 𝑣 by 𝑣 𝑏 ∗ and proceed to the next iteration.
There are 𝑑 = 𝑂(log 𝑛) iterations, each takes 𝑂(log 𝑛) bits of communication. Hence 𝜋 has
depth 𝑂(log2 𝑛), as required.
Remark 5.10. The strategy from the proof of Proposition 5.3 is efficient only in terms of the
number of rounds. In the next section, we present another version of this strategy. It will give
us not only low depth but also explicit polynomial-size circuits. For that, however, we require a
bit more from protocols for the 𝑄 𝑘 -communication games.
6 Effective version
Fix 𝑓 ∈ 𝑄 𝑘 . We say that a dag-like communication protocol 𝜋 strongly computes the 𝑄 𝑘 -
communication game for 𝑓 if for every terminal 𝑡 of 𝜋 and for every 𝑥 ∈ 𝑓 −1 (0) the following
holds. If 𝑥 is 𝑖-compatible with 𝑡 for some 𝑖 ∈ [𝑘], then 𝑥 𝑗 = 0, where 𝑗 = 𝑙(𝑡) is the label of the
terminal 𝑡 in the protocol 𝜋. In other words, there should be a path 𝑝 to 𝑡 such that, first, 𝑥 𝑙(𝑡) = 0,
and second, one of the parties is compatible with this path on input 𝑥. That is, for every node of
𝑝 from where this party is the one to communicate, it communicates along 𝑝 on 𝑥. We stress
that there might be no tuple from ( 𝑓 −1 (0)) 𝑘 which includes 𝑥 and visits 𝑡. Hence, a protocol
which computes the 𝑄 𝑘 -hypotheses game for 𝑓 might not compute it in the strong sense.
Similarly, fix 𝑓 ∈ 𝑅 𝑘 . We say that a dag-like communication protocol 𝜋 strongly computes the
𝑅 𝑘 -communication game for 𝑓 if for every terminal 𝑡 of 𝜋 and for every 𝑥 ∈ 𝑓 −1 (0) the following
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 22
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
holds. If 𝑥 is 𝑖-compatible with 𝑡 for some 𝑖 ∈ [𝑘], then 𝑥 𝑗 = 𝑏, where (𝑗, 𝑏) = 𝑙(𝑡) is the label of
the terminal 𝑡 in the protocol 𝜋.
Next, we prove an effective version of Proposition 5.3.
Theorem 6.1. For every constant 𝑘 ≥ 2 there exists a polynomial-time algorithm 𝐴 such that the following
holds. Assume that 𝑓 ∈ 𝑄 𝑘 and 𝜋 is a dag-like protocol which strongly computes the 𝑄 𝑘 -communication
game for 𝑓 . Then, given the light form of 𝜋, the algorithm 𝐴 outputs a 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 such that
depth(𝐶) is linear in depth(𝜋) and size(𝐶) is polynomial in size(𝜋).
Proof. Let 𝑑 = depth(𝜋). We will again give an 𝑂(𝑑)-round winning strategy of Learner in the
𝑄 𝑘 -hypotheses game for 𝑓 . This time, however, we will ensure that, given the light form of 𝜋,
the light form of our strategy can be computed in polynomial time (in particular, its size will be
polynomial in size(𝜋)). By Proposition 3.1, this will give us a 𝑄 𝑘 -circuit 𝐶 ≤ 𝑓 of depth 𝑂(𝑑)
whose size is polynomial in size(𝜋) and which is polynomial-time computable from the light
form of 𝜋.
Instead of specifying the light form of our strategy directly, we will use the following trick.
Assume that Learner has a working tape consisting of 𝑂(log size(𝜋)) cells, where each cell can
store one bit. Learner memorizes all the Nature’s responses so that it always knows the current
position of the game. But it does not store the sequence of Nature’s responses on the working
tape (there might be no space for it). Instead, it first makes its hypotheses which depend on the
current position. Then it receives a Nature’s response 𝑟 ∈ {0, 1, . . . , 𝑘}. And then it modifies the
working tape, but the result must depend only on the current content of the working tape and
on 𝑟 (and not on the current position in a game). Moreover, we will ensure that modifying the
working tape takes polynomial time given the light form of 𝜋.
The main purpose of the working tape manifests itself in the end. Namely, at some point,
Learner decides to stop making hypotheses. This should be indicated on the working tape.
More importantly, Learner’s output must depend only on the content of the working tape in
the end (and not on the whole sequence of Nature’s responses). Moreover, this should take
polynomial time to compute that output, given the light form of 𝜋.
If a strategy satisfies these restrictions, then its light form is polynomial-time computable
from the light form of 𝜋. Indeed, the underlying dag will consist of all possible configurations of
the working tape. Their number is polynomial in size(𝜋), because there are 𝑂(log size(𝜋)) bits
on the working tape. For all non-terminal configurations 𝑐 we go through all 𝑟 ∈ {0, 1, . . . , 𝑘}.
We compute what would be a configuration 𝑐 𝑟 of the working tape if the current configuration
is 𝑐 and Nature’s response is 𝑟. After that we connect 𝑐 to 𝑐0 , 𝑐1 , . . . , 𝑐 𝑘 . Finally, we compute the
outputs of Learner in all terminal configurations. This gives the light form of our strategy in
time polynomial in size(𝜋).
Let 𝑉 be the set of nodes of 𝜋 and 𝑇 be the set of terminals of 𝜋. We will work with
multidimensional arrays of nodes. Namely, we will consider 𝑘-dimensional arrays in which every
dimension is indexed by integers from [𝑘]. Formally, such arrays are functions of the form
𝑀 : [𝑘] 𝑘 → 𝑉. We will use the notation 𝑀[𝑐 1 , . . . , 𝑐 𝑘 ] for the value of 𝑀 on (𝑐1 , . . . , 𝑐 𝑘 ) ∈ [𝑘] 𝑘 .
We will use a slightly stronger notion of completeness than in the proof of Proposition 5.3.
Definition 6.2. We say that a multidimensional array 𝑀 : [𝑘] 𝑘 → 𝑉 is complete for a set
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 23
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
𝒵 ⊆ 𝑓 −1 (0) if there exists a function 𝑔 : 𝒵 → [𝑘] such that the following holds. For every
𝑧 ∈ 𝒵, for every 𝑖 ∈ [𝑘] and for every (𝑐1 , . . . , 𝑐 𝑘 ) ∈ [𝑘] 𝑘 such that 𝑐 𝑖 = 𝑔(𝑧) it holds that the
node 𝑀[𝑐 1 , . . . , 𝑐 𝑘 ] is 𝑖-compatible with 𝑧 in the protocol 𝜋. We also say that such 𝑔 establishes
completeness of 𝑀 for 𝒵.
We stress that in this definition 𝑀[𝑐1 , . . . , 𝑐 𝑘 ] should be 𝑖-compatible with 𝑧 even if there
is no tuple (𝑧1 , . . . , 𝑧 𝑘 ) with (𝑔(𝑧1 ), . . . , 𝑔(𝑧 𝑘 )) = (𝑐1 , . . . , 𝑐 𝑘 ). Intuitively, we can afford such a
strong notion of completeness (compared to the proof of Proposition 5.3) because this time 𝜋
computes the 𝑄 𝑘 -communication game for 𝑓 in the strong sense.
We now describe the Learner’s strategy. It proceeds in 𝑑 iterations, each iteration takes 𝑂(1)
rounds of the 𝑄 𝑘 -hypotheses game. The working tape of Learner consists of:
• an integer 𝑖𝑡𝑒𝑟;
• a multidimensional array 𝑀 : [𝑘] 𝑘 → 𝑉;
• 𝑂(1) additional bits of memory.
The integer 𝑖𝑡𝑒𝑟 will never exceed 𝑑 ≤ size(𝜋), so to store all this information we will need
𝑂(log(size(𝜋))) bits, as required. At each moment, 𝑖𝑡𝑒𝑟 equals the number of iterations
performed so far (at the beginning, 𝑖𝑡𝑒𝑟 = 0). Learner updates 𝑀 only at moments when 𝑖𝑡𝑒𝑟 is
incremented by 1. So let 𝑀 ℎ denote the content of the array 𝑀 when 𝑖𝑡𝑒𝑟 = ℎ (that is, after ℎ
iterations). Learner stops making hypotheses when 𝑖𝑡𝑒𝑟 = 𝑑 (that is, after 𝑑 iterations).
We call an array of nodes ℎ-low if every node in it is either a terminal or of depth at least ℎ.
Learner maintains the following invariant.
Invariant 6.3. 𝑀 ℎ is ℎ-low and 𝑀 ℎ is complete for the set 𝒵ℎ of all 𝑧 ∈ 𝑓 −1 (0) that are compatible
with Nature’s responses after ℎ iterations.
At the beginning, Learner sets every element of 𝑀0 to be the starting node of 𝜋 so that
Invariant 6.3 trivially holds.
Now, let us show that when 𝑖𝑡𝑒𝑟 = 𝑑, Learner is able to output a correct answer to the
𝑄 𝑘 -hypotheses game in polynomial time, knowing only the current content of the working tape
and the light form of 𝜋. Indeed, observe that 𝑀 𝑑 consists only of terminals. Hence it is sufficient
to establish the following lemma.
Lemma 6.4. Assume that 𝑀 : [𝑘] 𝑘 → 𝑇 is complete for 𝒵 ⊆ 𝑓 −1 (0). Let 𝑙 be the output of 𝜋 in the
terminal 𝑀[1, 2, . . . , 𝑘]. Then 𝑧 𝑙 = 0 for every 𝒵.
Proof. Since 𝜋 strongly computes the 𝑄 𝑘 -communication game for 𝑓 , it is enough to show that
every 𝑧 ∈ 𝒵 is 𝑖-compatible with 𝑀[1, 2, . . . , 𝑘] for some 𝑖 ∈ [𝑘]. Take 𝑔 : 𝒵 → [𝑘] establishing
completeness of 𝑀 for 𝒵. By definition, 𝑧 is 𝑔(𝑧)-compatible with 𝑀[1, 2, . . . , 𝑘].
Finally, we need to perform an iteration. Assume that ℎ iterations passed and Invariant 6.3
still holds. Let 𝑈 ℎ be the set of nodes appearing in 𝑀 ℎ . Take any function 𝑔 : 𝒵ℎ → [𝑘]
establishing completeness of 𝑀 ℎ for 𝒵ℎ .
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 24
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
For any 𝑧 ∈ 𝑓 −1 (0) we denote by 𝑝 𝑧 a communication profile of 𝑧 with respect to 𝑈 ℎ (we use
the same notion of a communication profile as in the proof of Proposition 5.3). Recall that 𝑝 𝑧 is
an element of {0, 1}𝑈 ℎ , i. e., a function from 𝑈 ℎ to {0, 1}. Learner wants to gain some information
about the pair (𝑝 𝑧 , 𝑔(𝑧)). In the beginning, Learner only knows that (𝑝(𝑧), 𝑔(𝑧)) ∈ {0, 1}𝑈 ℎ × [𝑘].
His goal is to narrow down the set of all possible values of the pair (𝑝(𝑧), 𝑔(𝑧)) to 𝑘 values. He
does so in the same manner as in the proof of Proposition 5.3. Namely, in each round Learner
asks Nature to specify some (𝑝, 𝑐) ∈ {0, 1}𝑈 ℎ × [𝑘] such that (𝑝 𝑧 , 𝑔(𝑧)) ≠ (𝑝, 𝑐). Learner can
do this until there are only 𝑘 pairs from (𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 ) ∈ {0, 1}𝑈 ℎ × [𝑘] left which are not
rejected by Nature. Learner stores each rejected (𝑝, 𝑐) on the working tape so that in the end he
knows (𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 ). This takes 2|𝑈 ℎ | · 𝑘 − 𝑘 = 𝑂(1) rounds of the 𝑄 𝑘 -hypotheses game
and 𝑂(1) additional bits of memory (we will free this memory once we compute 𝑀 ℎ+1 so that
we can use it again in the next iteration). After that, the (ℎ + 1)st iteration is finished. Let us
observe that for any 𝑧 which is compatible with the Nature’s responses after ℎ + 1 iterations it
holds that (𝑝 𝑧 , 𝑔(𝑧)) ∈ {(𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 )}, i.e,
(𝑝 𝑧 , 𝑔(𝑧)) ∈ {(𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 )} for all 𝑧 ∈ 𝒵ℎ+1 . (6.1)
After that, Learner updates 𝑀 ℎ . He only needs to know (𝑝 1 , 𝑐1 ), . . . , (𝑝 𝑘 , 𝑐 𝑘 ) (they can be
extracted from the content of the working tape) and the light form of 𝜋. Namely, Learner deter-
mines 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] for (𝑑1 , . . . , 𝑑 𝑘 ) ∈ [𝑘] 𝑘 as follows. Consider the node 𝑣 = 𝑀 ℎ [𝑐 𝑑1 , . . . , 𝑐 𝑑 𝑘 ].
If 𝑣 is a terminal, then set 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] = 𝑣. Otherwise, let 𝑖 ∈ [𝑘] be the index of the party
communicating at 𝑣. Look at 𝑝 𝑑𝑖 , it is a function from 𝑈 ℎ to {0, 1}. Define 𝑟 = 𝑝 𝑑𝑖 (𝑣). Among
two edges, starting at 𝑣, choose one which is labeled by 𝑟. Descend along this edge from 𝑣 and
let the resulting successor of 𝑣 be 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ].
Obviously, computing 𝑀 ℎ+1 takes time polynomial in size(𝜋). To show that Invariant 6.3 is
maintained, we have to show that (a) 𝑀 ℎ+1 is (ℎ + 1)-low and (b) 𝑀 ℎ+1 is complete for 𝒵ℎ+1 .
The first part, (a), holds because each 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] is either a terminal or a successor of
a node of depth at least ℎ. For (b) we define the following function:
𝑔 0 : 𝒵ℎ+1 → [𝑘], 𝑔 0(𝑧) = 𝑖, where 𝑖 is such that (𝑝 𝑧 , 𝑔(𝑧)) = (𝑝 𝑖 , 𝑐 𝑖 ).
By (6.1) this definition is correct. We will show that 𝑔 0 establishes completeness of 𝑀 ℎ+1 for
𝒵ℎ+1 .
For that, take any 𝑧 ∈ 𝒵ℎ+1 , 𝑖 ∈ [𝑘] and (𝑑1 , . . . , 𝑑 𝑘 ) ∈ [𝑘] 𝑘 such that 𝑑 𝑖 = 𝑔 0(𝑧). We shall
show that 𝑧 is 𝑖-compatible with a node 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ]. By definition of 𝑔 0, we have that
𝑔(𝑧) = 𝑐 𝑑𝑖 . Recall that the function 𝑔 establishes completeness of 𝑀 ℎ for 𝒵ℎ . This means that 𝑧
is 𝑖-compatible with 𝑣 = 𝑀[𝑐 𝑑1 , . . . , 𝑐 𝑑 𝑘 ]. If 𝑣 is a terminal, then 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] = 𝑣 and there
is nothing left to prove.
Otherwise, 𝑣 ∈ 𝑉 \ 𝑇. Let 𝑗 be the index of the party communicating at 𝑣. By definition,
𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] is a successor of 𝑣. If 𝑗 ≠ 𝑖, then any successor of 𝑣 is 𝑖-compatible with 𝑧
(because the 𝑗th party communicates at 𝑣, not the 𝑖th one). Finally, assume that 𝑗 = 𝑖. The node
𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ] is obtained from 𝑣 by descending along the edge which is labeled by 𝑟 = 𝑝 𝑑𝑖 (𝑣).
Hence, to show that 𝑧 is 𝑖-compatible with 𝑀 ℎ+1 [𝑑1 , . . . , 𝑑 𝑘 ], we should verify that the 𝑖th party
transmits 𝑟 at 𝑣 on input 𝑧. Recall that 𝑔 0(𝑧) = 𝑑 𝑖 , which by definition of 𝑔 0 means that 𝑝 𝑧 = 𝑝 𝑑𝑖 .
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 25
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
That is, 𝑝 𝑑𝑖 is the communication profile of 𝑧 with respect to 𝑈 ℎ . In particular, 𝑟 = 𝑝 𝑑𝑖 (𝑣) = 𝑝 𝑧 (𝑣)
is the bit transmitted by the 𝑖th party on input 𝑧 at 𝑣, as required.
By the same argument, one can obtain an analog of the previous theorem for the 𝑅 𝑘 case.
Theorem 6.5. For every constant 𝑘 ≥ 2 there exists a polynomial-time algorithm 𝐴 such that the following
holds. Assume that 𝑓 ∈ 𝑅 𝑘 and 𝜋 is a dag-like protocol which strongly computes the 𝑅 𝑘 -communication
game for 𝑓 . Then, given the light form of 𝜋, the algorithm 𝐴 outputs an 𝑅 𝑘 -circuit 𝐶 ≤ 𝑓 such that
depth(𝐶) is linear in depth(𝜋) and size(𝐶) is polynomial in size(𝜋).
7 Derivation of Theorems 1.1 and 1.3
In this section, we obtain Theorems 1.1 and 1.3 by devising protocols strongly computing the
corresponding 𝑄 𝑘 -communication games. Unfortunately, establishing strong computability
requires diving into straightforward but tedious technical details, even for simple protocols.
Alternative proof of Theorem 1.1. We will show that there exists a protocol 𝜋 of depth 𝑂(log 𝑛)
with a polynomial-time computable light form, strongly computing the 𝑄 2 -communication
game for MAJ2𝑛+1 . By Theorem 6.1, this means that there is a polynomial-time computable
MAJ3 -formula 𝐹 ≤ MAJ2𝑛+1 of depth 𝑂(log 𝑛). From the self-duality of MAJ2𝑛+1 and MAJ3 it
follows that 𝐹 computes MAJ2𝑛+1 .
Due to the AKS sorting network, there exists a polynomial-time computable monotone
formula 𝐹0 of depth 𝑂(log 𝑛) for MAJ2𝑛+1 . Consider the following communication protocol 𝜋.
The tree of 𝜋 coincides with the tree of 𝐹0. Inputs to 𝐹0 will be leaves of 𝜋. In a leaf containing an
input variable 𝑥 𝑖 the output of the protocol 𝜋 is 𝑖. Remaining nodes of 𝜋 are ∧-gates and ∨-gates.
The first party communicates in ∧-gates, while the second party communicates in ∨-gates. Let
us now define how the parties communicate.
Fix an ∧-gate 𝑔 (which belongs to the first party). Let 𝑔0 , 𝑔1 be gates that are fed to 𝑔, i. e.,
𝑔 = 𝑔0 ∧ 𝑔1 . There are two edges, starting at 𝑔, one leads to 𝑔0 (and is labeled by 0) and the other
leads to 𝑔1 (and is labeled by 1). Take an input 𝑎 ∈ MAJ−1 2𝑛+1 (0) to the first party. Having input 𝑎,
the first party transmits the bit 𝑟 = min{𝑐 ∈ {0, 1} | 𝑔 𝑐 (𝑎) = 0} at the gate 𝑔. If the minimum is
over the empty set, we set 𝑟 = 0.
Take now an ∨-gate ℎ (belonging to the second party). Similarly, there are two edges starting
at ℎ, one leads to a gate ℎ 0 (and is labeled by 0) and the other leads to a gate ℎ1 (and is labeled by
1). Take an input 𝑏 ∈ MAJ−1 2𝑛+1 (0) to the second party. Having input 𝑏, the second party transmits
the bit 𝑟 = min{𝑐 ∈ {0, 1} | ℎ 𝑐 (¬𝑏) = 1} at the gate ℎ. If the minimum is over the empty set, then
we set 𝑟 = 0. Here ¬ denotes the bitwise negation. Description of the protocol 𝜋 is finished.
Clearly, the protocol 𝜋 is of depth 𝑂(log 𝑛) and its light form is polynomial-time computable.
It remains to argue that the protocol strongly computes the 𝑄 2 -communication game for
MAJ2𝑛+1 . Nodes of the protocol may be identified with gates of 𝐹0. Consider any path
𝑝 = h𝑒1 , . . . , 𝑒 𝑚 i in the protocol 𝜋 which starts in the output gate 𝑔 0 . Assume that 𝑒 𝑗 is an edge
from 𝑔 𝑗−1 to 𝑔 𝑗 . We shall show the following: if 𝑎 ∈ MAJ−1 2𝑛+1 (0) is 1-compatible with 𝑝, then
𝑔 0 (𝑎) = 𝑔 1 (𝑎) = . . . = 𝑔 𝑚 (𝑎) = 0. Indeed, 𝑔 0 (𝑎) = 0 holds because 𝐹0 computes MAJ2𝑛+1 . Now,
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 26
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
assume that 𝑔 𝑗 (𝑎) = 0 is already proved. If 𝑔 𝑗 is an-∨ gate, then 𝑔 𝑗+1 (𝑎) = 0 just because 𝑔 𝑗+1
feds to 𝑔 𝑗 . Otherwise, 𝑔 𝑗 is an ∧-gate which therefore belongs to the first party. Let 𝑟 ∈ {0, 1} be
𝑗 𝑗 𝑗
the label of the edge 𝑒 𝑗+1 . Note that 𝑔 𝑗+1 = 𝑔 𝑟 , where 𝑔0 , 𝑔1 are two gates which are fed to 𝑔 𝑗 .
Since 𝑎 is 1-compatible with 𝑝, it holds that 𝑟 coincides with the bit that the first party transmits
𝑗
at 𝑔 𝑗 on input 𝑎, i. e., with min{𝑐 ∈ {0, 1} | 𝑔 𝑐 (𝑎) = 0}. The set over which the minimum is
taken is non-empty, because 𝑔 𝑗 (𝑎) = 0. In particular, 𝑟 belongs to this set, which means that
𝑗
𝑔 𝑗+1 (𝑎) = 𝑔 𝑟 (𝑎) = 0, as required.
Similarly, one can verify that if 𝑏 ∈ MAJ−12𝑛+1 (0) is 2-compatible with 𝑝, then 𝑔 (¬𝑏) = 𝑔 (¬𝑏) =
0 1
. . . = 𝑔 𝑚 (¬𝑏) = 0. Overall, we get that if a leaf 𝑙 contains a variable 𝑥 𝑖 and 𝑙 is 1-compatible with
𝑎 then 𝑎 𝑖 = 0, and if 𝑙 is 2-compatible with 𝑏 then ¬𝑏 𝑖 = 1.
Hence the protocol strongly computes the 𝑄 2 -communication game for MAJ2𝑛+1 .
Proof of Theorem 1.3. We will use the same protocol as in the proof of Corollary 5.9. This time,
however, we have to define its light form more explicitly. We will obtain polynomial-size dag-like
protocol of depth 𝑂(log2 𝑛) with a polynomial-time computable light form, which strongly
𝑘𝑛+1
computes the 𝑄 𝑘 -communication game for THR𝑛+1 . By Theorem 6.1, this means that there is a
𝑘𝑛+1
polynomial-time computable 𝑄 𝑘 -circuit 𝐶 ≤ THR𝑛+1 of depth 𝑂(log2 𝑛). By an argument from
𝑘𝑛+1
Corollary 5.9, the circuit 𝐶 coincides with THR𝑛+1 .
We will use the same tree 𝑇 as in the proof of Corollary 5.9. That is, 𝑇 is a tree of depth
𝑂(log 𝑛) with 𝑘𝑛 + 1 leaves. We identify its leaves with elements of [𝑘𝑛 + 1]. Every node 𝑣 of
𝑇 is associated with the set 𝑇𝑣 ⊆ [𝑘𝑛 + 1] of leaves that are descendants of 𝑣. We also use a
notation supp(𝑥) = {𝑖 ∈ [𝑘𝑛 + 1] | 𝑥 𝑖 = 1} for 𝑥 ∈ {0, 1} 𝑘𝑛+1 .
Let us specify the underlying dag 𝐺 of our protocol 𝜋. For a node 𝑣 of 𝑇, let 𝒮𝑣 be the set of
all tuples (𝑠 1 , 𝑠2 , . . . , 𝑠 𝑘 ) ∈ {0, 1, . . . , 𝑘𝑛 + 1} 𝑘 such that 𝑠 1 + 𝑠2 + . . . + 𝑠 𝑘 < |𝑇𝑣 |. For every node
𝑣 of 𝑇 and for every (𝑠 1 , 𝑠2 , . . . , 𝑠 𝑘 ) ∈ 𝒮𝑣 the dag 𝐺 will contain a node identified with a tuple
(𝑣, 𝑠1 , 𝑠2 , . . . , 𝑠 𝑘 ). These nodes of 𝐺 will be called main nodes (there will be some other nodes
too). Observe that the number of main nodes is polynomial in 𝑛. The starting node of 𝐺 will be
(𝑟, 𝑛, . . . , 𝑛), where 𝑟 is the root of 𝑇. Note that if 𝑙 is a leaf of 𝑇, then |𝑇𝑙 | = 1. Hence, the only
main node having 𝑙 as the first coordinate is (𝑙, 0, . . . , 0). The set of terminals of 𝜋 will coincide
with the set of all main nodes of the form (𝑙, 0, . . . , 0), where 𝑙 is a leaf of 𝑇. The output of 𝜋 in
(𝑙, 0, . . . , 0) is 𝑙.
The communication in 𝜋 is arranged as follows. First, we assume for simplicity that every
party has a vector with exactly 𝑛 ones (if there are less than 𝑛 ones, one can add a necessary
amount of ones to the input). The communication proceeds in 𝑂(log 𝑛) phases. In the beginning
of each phase, the parties belong to some main node (𝑣, 𝑠1 , . . . , 𝑠 𝑘 ). Then the first party sends
two non-negative integers that sum up to 𝑠 1 . After that, the second party sends two non-
negative integers that sum up to 𝑠 2 , and so on. More specifically, if the input to the 𝑖th party is
𝑥 ∈ {0, 1} 𝑘𝑛+1 and |𝑇𝑣 ∩ supp(𝑥)| ≤ 𝑠 𝑖 , then the 𝑖th party sends |𝑇𝑣0 ∩ supp(𝑥)| and |𝑇𝑣1 ∩ supp(𝑥)|,
where 𝑣 0 and 𝑣 1 are two successors of 𝑣. Otherwise, it sends any two numbers that sum up to 𝑠 𝑖 .
When all the numbers are sent, the parties move to some other main node. More specifically,
let 𝑎 𝑖 and 𝑏 𝑖 be numbers sent by the 𝑖th party. If 𝑎 1 + . . . + 𝑎 𝑘 < |𝑇𝑣0 |, the parties move the main
node (𝑣0 , 𝑎1 , . . . , 𝑎 𝑘 ). Now, assume that 𝑎 1 + . . . + 𝑎 𝑘 ≥ |𝑇𝑣0 |. We claim that in this case we have
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 27
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
𝑏1 + . . . + 𝑏 𝑘 < |𝑇𝑣1 |. This is because by definition (𝑎 1 + . . . + 𝑎 𝑘 ) + (𝑏1 + . . . + 𝑏 𝑘 ) = 𝑠 1 + . . . + 𝑠 𝑘 <
|𝑇𝑣 | = |𝑇𝑣0 | + |𝑇𝑣1 |. So if 𝑎 1 + . . . + 𝑎 𝑘 ≥ |𝑇𝑣0 |, the parties move to the main node (𝑣 1 , 𝑏1 , . . . , 𝑏 𝑘 ).
Observe that if the input to the 𝑖th party, 𝑥, has exactly 𝑛 ones, then throughout any execution
of the protocol we have |𝑇𝑣 ∩ supp(𝑥)| = 𝑠 𝑖 , where (𝑣, 𝑠1 , . . . , 𝑠 𝑘 ) is our current main node. In
other words, if a vector 𝑥 ∈ {0, 1} 𝑘𝑛+1 with 𝑛 ones is 𝑖-compatible with a main node (𝑣, 𝑠1 , . . . , 𝑠 𝑘 ),
then |𝑇𝑣 ∩ supp(𝑥)| = 𝑠 𝑖 . This implies that 𝜋 strongly computes the 𝑄 𝑘 -communication game for
𝑘𝑛+1
THR𝑛+1 . Indeed, if a terminal (𝑙, 0, . . . , 0) is 𝑖-compatible with 𝑥, then |𝑙 ∩ supp(𝑥)| = 0, that is,
𝑥 𝑙 = 0. In other words, the output of 𝜋 in (𝑙, 0, . . . , 0) is a correct answer for 𝑥, as required.
Overall, the light form of 𝜋 looks as follows. It consists of polynomially many main nodes
that are arranged in a tree of depth 𝑂(log 𝑛). Each main node has a protocol of depth 𝑂(log 𝑛)
attached to it. The leaves of this protocol are merged with some main nodes on the next level
of 𝑇. Thus, 𝜋 is of depth 𝑂(log2 𝑛) and polynomial size, and its light form is polynomial-time
computable.
8 Direct proof of Theorem 1.1
In this section we distill from our argument a direct proof of Theorem 1.1.We show that there
exists a deterministic polynomial-time algorithm performing the following transformation
• Input: a monotone formula 𝐹 of depth 𝑑 computing MAJ2𝑛+1 ;
• Output: a MAJ3 -formula Φ of depth 𝑑 + 𝑂(log 𝑛) computing MAJ2𝑛+1 .
The existence of such an algorithm implies Theorem 1.1. Indeed, take the AKS sorting
network and extract from it a polynomial-time computable monotone formula of depth 𝑂(log 𝑛)
computing MAJ2𝑛+1 . Then just plug 𝐹 into the transformation above. So it only remains to
explain how to perform this transformation in polynomial time.
≤𝑛 we denote the set of all (2𝑛 + 1)-bit vectors with at most 𝑛 ones.
In the proof by {0, 1}2𝑛+1
This is also the set of vectors where MAJ2𝑛+1 equals 0. For 𝑥 ∈ {0, 1}2𝑛+1 we denote by ¬𝑥 the
bitwise negation of 𝑥.
The following observation simplifies our task.
Observation 8.1. Assume that Φ is a MAJ3 -formula and
Φ(𝑥) = 0 for any 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 .
Then Φ computes MAJ2𝑛+1 .
Proof. It is already given that Φ equals 0 everywhere, where MAJ2𝑛+1 equals 0. It remains to
show that Φ equals 1 everywhere, where MAJ2𝑛+1 equals 1. For that, we take any 𝑥 ∈ {0, 1}2𝑛+1
with at least 𝑛 + 1 ones and show that Φ(𝑥) = 1. Formula Φ is constructed from self-dual gates
and hence computes a self-dual function (recall that a Boolean function is self-dual if it takes
opposite values in opposite vertices of the Boolean cube). This means that Φ(𝑥) = ¬Φ(¬𝑥).
Finally, notice that Φ(¬𝑥) = 0 because ¬𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 .
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 28
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
The construction can naturally be split into two independent steps.
• Step 1. For any two distinct 𝑖, 𝑗 ∈ [2𝑛 + 1] construct from 𝐹 a MAJ3 -formula Φ𝑖,𝑗 of depth 𝑑
(i. e., of the same depth as 𝐹) such that
Φ𝑖,𝑗 (𝑥) = 0 for any 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 such that 𝑥 𝑖 + 𝑥 𝑗 = 1.
• Step 2. Assemble from the formulas Φ𝑖,𝑗 a MAJ3 -formula Φ of depth 𝑑 + 𝑂(log 𝑛) satisfying
Φ(𝑥) = 0 for all 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 .
By Observation 8.1 the formula Φ from the step 2 will compute MAJ2𝑛+1 .
Step 1. We obtain Φ𝑖,𝑗 from 𝐹 in a way described in Figure 2. We only have to show that
Formula F Formula Φi,j
∧ MAJ3
g1 g2 g1 g2 xi
∨ MAJ3
∨ MAJ3
∧
g1 g2 g1 g2 xj MAJ3
x1 x2 x2n+1 x1 x2 x2n+1
Figure 2: Transforming 𝐹 into Φ𝑖,𝑗 .
for all 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 with 𝑥 𝑖 + 𝑥 𝑗 = 1 we have Φ𝑖,𝑗 (𝑥) = 0. The argument is different for the
following two cases.
• Case 1: 𝑥 𝑖 = 0 and 𝑥 𝑗 = 1.
• Case 2: 𝑥 𝑖 = 1 and 𝑥 𝑗 = 0.
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 29
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
Both cases rely on the following observation. Notice that Φ𝑖,𝑗 (𝑥) = MAJ2𝑛+1 (𝑥) for all 𝑥 ∈
{0, 1}2𝑛+1 with 𝑥 𝑖 = 0, 𝑥 𝑗 = 1. This is because when we plug in 𝑥 𝑖 = 0, 𝑥 𝑗 = 1 into Φ𝑖,𝑗 , we obtain
a formula which is equivalent to 𝐹. Indeed, every MAJ3 -gate in Φ𝑖,𝑗 that were obtained from
an ∧-gate of 𝐹 turns back into an ∧-gate. Similarly, every MAJ3 -gate in Φ𝑖,𝑗 that were obtained
from an ∨-gate of 𝐹 turns back into an ∨-gate. To see this, note that MAJ3 (𝑔1 , 𝑔2 , 0) = 𝑔1 ∧ 𝑔2
and MAJ3 (𝑔1 , 𝑔2 , 1) = 𝑔1 ∨ 𝑔2 .
Case 1. This is an immediate consequence of the above observation. Formula Φ𝑖,𝑗 coincides
with MAJ2𝑛+1 every time 𝑥 𝑖 = 0, 𝑥 𝑗 = 1, and for 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 we have MAJ2𝑛+1 (𝑥) = 0.
Case 2. Here we use a self-duality argument. Consider the bitwise negation of 𝑥. Since
¬𝑥 has at least 𝑛 + 1 ones, we have MAJ2𝑛+1 (¬𝑥) = 1. Next, since (¬𝑥)𝑖 = 0, (¬𝑥) 𝑗 = 1, we
have Φ𝑖,𝑗 (¬𝑥) = MAJ2𝑛+1 (¬𝑥) = 1 by our observation. Finally, due to self-duality, Φ𝑖,𝑗 (𝑥) =
¬Φ𝑖,𝑗 (¬𝑥) = 0, as required.
Step 2. We show that for any 𝑆 ⊆ [2𝑛 + 1], |𝑆| ≥ 2 one can construct (in deterministic
polynomial time) a MAJ3 -formula Φ𝑆 of depth at most 𝑑 + 1 + log9/8 (|𝑆|) such that:
Φ𝑆 (𝑥) = 0 for all 𝑥 ∈ {0, 1}2𝑛+1
≤𝑛 such that 𝑥 𝑖 = 0 for some 𝑖 ∈ 𝑆.
By setting Φ = Φ[2𝑛+1] we obtain a formula which is 0 everywhere on {0, 1}2𝑛+1 ≤𝑛 , as required.
Indeed, every 𝑥 ∈ {0, 1} ≤𝑛 has a 0-coordinate in [2𝑛 + 1].
2𝑛+1
The construction is recursive. Assume first that |𝑆| ≥ 3. Partition 𝑆 into 3 disjoint subsets
𝑆1 , 𝑆2 , 𝑆3 of sizes b|𝑆|/3c, b|𝑆|/3c and |𝑆| − 2b|𝑆|/3c. Construct recursively Φ𝑆1 ∪𝑆2 , Φ𝑆1 ∪𝑆3 , Φ𝑆2 ∪𝑆3
and then set
Φ𝑆 = MAJ3 (Φ𝑆1 ∪𝑆2 , Φ𝑆1 ∪𝑆3 , Φ𝑆2 ∪𝑆3 ) .
If |𝑆| = 2 and 𝑆 = {𝑖, 𝑗}, set
Φ{𝑖,𝑗} = MAJ3 (Φ𝑖,𝑗 , 𝑥 𝑖 , 𝑥 𝑗 ),
where Φ𝑖,𝑗 is from the previous step. Description of the construction is finished. It remains to
explain why this construction is correct, why the depth of Φ𝑆 is at most 𝑑 + 1 + log9/8 (|𝑆|) and
why the construction takes polynomial time.
• A recursive call is always for sets of smaller size. More specifically, it holds that:
8
|𝑆1 ∪ 𝑆2 |, |𝑆1 ∪ 𝑆3 |, |𝑆2 ∪ 𝑆3 | ≤ · |𝑆|. (8.1)
9
Indeed, the sizes of 𝑆1 ∪ 𝑆2 , 𝑆1 ∪ 𝑆3 , 𝑆2 ∪ 𝑆3 do not exceed |𝑆| − b|𝑆|/3c ≤ |𝑆| − |𝑆|/3 + 2/3 =
2/3 · (|𝑆| + 1) ≤ 2/3 · (|𝑆| + |𝑆|/3) = 8/9 · |𝑆|.
• We now show, by induction on |𝑆|, that Φ𝑆 (𝑥) = 0 for all 𝑥 ∈ {0, 1}2𝑛+1 ≤𝑛 that have a
0-coordinate in 𝑆. First, consider the case 𝑆 = {𝑖, 𝑗}. If there are exactly one 0-coordinate
among 𝑖, 𝑗, then by definition Φ𝑖,𝑗 (𝑥) = 0 and hence Φ{𝑖,𝑗} (𝑥) = MAJ3 (Φ𝑖,𝑗 (𝑥), 𝑥 𝑖 , 𝑥 𝑗 ) =
MAJ3 (0, 0, 1) = 0. If both 𝑥 𝑖 = 0 and 𝑥 𝑗 = 0, then Φ{𝑖,𝑗} (𝑥) = MAJ3 (Φ𝑖,𝑗 (𝑥), 0, 0) = 0.
Now, consider the case |𝑆| ≥ 3. A 0-coordinate of 𝑥 lying in 𝑆 lies also in exactly
2 sets out of 𝑆1 ∪ 𝑆2 , 𝑆1 ∪ 𝑆3 , 𝑆2 ∪ 𝑆3 . Hence, by the induction hypothesis, among
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 30
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
Φ𝑆1 ∪𝑆2 (𝑥), Φ𝑆1 ∪𝑆3 (𝑥), Φ𝑆2 ∪𝑆3 (𝑥) there are at least 2 zeroes. This means that Φ𝑆 (𝑥) =
MAJ3 (Φ𝑆1 ∪𝑆2 (𝑥), Φ𝑆1 ∪𝑆3 (𝑥), Φ𝑆2 ∪𝑆3 (𝑥)) = 0.
• Again, by induction on |𝑆| one can show that
depth(𝑆) ≤ 𝑑 + 1 + log9/8 (|𝑆|),
For 𝑆 = {𝑖, 𝑗} the depth of Φ{𝑖,𝑗} is depth(Φ𝑖,𝑗 ) + 1 = 𝑑 + 1 ≤ 𝑑 + 1 + log5/4 (|𝑆|). For |𝑆| ≥ 3
assume that the claim is proved for Φ𝑆1 ∪𝑆2 , Φ𝑆1 ∪𝑆3 , Φ𝑆2 ∪𝑆3 . Then
depth(Φ𝑆 ) = 1 + max {depth(Φ𝑆1 ∪𝑆2 ), depth(Φ𝑆1 ∪𝑆3 ), depth(Φ𝑆2 ∪𝑆3 )}
8
≤ 1 + 𝑑 + 1 + log9/8 · |𝑆|
9
= 𝑑 + 1 + log9/8 (|𝑆|).
In the second line, we use the induction hypothesis (8.1).
• Similarly, the tree of recursive calls for Φ𝑆 has depth at most log9/8 (|𝑆|) and hence
polynomial size. Therefore, the whole construction takes polynomial time.
9 Open problems
𝑘𝑛+1
• Can the 𝑄 𝑘 -communication game for THR𝑛+1 be solved in 𝑜(log2 𝑛) bits of communication
𝑘𝑛+1
for 𝑘 ≥ 3? Equivalently, can THR𝑛+1 be computed by a 𝑄 𝑘 -circuit of depth 𝑜(log2 𝑛) ? Or
at least by an 𝑅 𝑘 -circuit of depth 𝑜(log2 𝑛) ?
• Are there any other interesting functions in 𝑄 𝑘 and 𝑅 𝑘 which can be analyzed with our
technique?
References
[1] Miklós Ajtai, János Komlós, and Endre Szemerédi: Sorting in 𝑐 log 𝑛 parallel steps.
Combinatorica, 3(1):1–19, 1983. Preliminary version in STOC’83. [doi:10.1007/BF02579338]
2, 15
[2] Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz,
and Ron D. Rothblum: Efficient multiparty protocols via log-depth threshold formulae.
In Proc. 33rd Ann. Internat. Cryptology Conf. (CRYPTO’13), pp. 185–202. Springer, 2013.
[doi:10.1007/978-3-642-40084-1_11, ECCC:TR13-107] 2, 3, 4, 5
[3] Irit Dinur and Or Meir: Toward the KRW composition conjecture: Cubic formula
lower bounds via communication complexity. Comput. Complexity, 27(3):375–462, 2018.
Preliminary version in CCC’16. [doi:10.1007/s00037-017-0159-x] 2
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 31
A LEXANDER KOZACHINSKIY AND V LADIMIR P ODOLSKII
[4] Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson: Toward better formula
lower bounds: The composition of a function and a universal relation. SIAM J. Com-
put., 46(1):114–131, 2017. Preliminary version in STOC’14. [doi:10.1137/15M1018319,
ECCC:TR13-190] 2
[5] Oded Goldreich: On (Valiant’s) polynomial-size monotone formula for majority. In Oded
Goldreich, editor, Computational Complexity and Property Testing: On the Interplay Between
Randomness and Computation, pp. 17–23. Springer, 2020. Earlier versions on author’s website:
2011 version, 2019 version. [doi:10.1007/978-3-030-43662-9_3] 2
[6] Mika Göös and Toniann Pitassi: Communication lower bounds via critical block
sensitivity. SIAM J. Comput., 47(5):1778–1806, 2018. Preliminary version in STOC’14.
[doi:10.1137/16M1082007] 2
[7] Arvind Gupta and Sanjeev Mahajan: Using amplification to compute majority with small
majority gates. Comput. Complexity, 6(1):46–63, 1996. [doi:10.1007/BF01202041] 3
[8] Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Springer, 2012. Summary
in Bull. EATCS 2014. [doi:10.1007/978-3-642-24508-4] 9
[9] Mauricio Karchmer, Ran Raz, and Avi Wigderson: Super-logarithmic depth lower bounds
via the direct sum in communication complexity. Comput. Complexity, 5(3–4):191–204, 1995.
Preliminary version in SCT’91. [doi:10.1007/BF01206317] 2
[10] Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require
super-logarithmic depth. SIAM J. Discr. Math., 3(2):255–265, 1990. Preliminary version in
STOC’88. [doi:10.1137/0403021] 1
[11] Alexander Kozachinskiy and Vladimir Podolskii: Multiparty Karchmer–Wigderson games
and threshold circuits. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 24:1–23. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.24] 1
[12] Anup Rao and Amir Yehudayoff: Communication Complexity and Applications. Cambridge
Univ. Press, 2020. [doi:10.1017/9781108671644] 1
[13] Ran Raz and Pierre McKenzie: Separation of the monotone NC hierarchy. Combinatorica,
19(3):403–435, 1999. Preliminary version in FOCS’97. [doi:10.1007/s004930050062] 2
[14] Dmitry Sokolov: Dag-like communication and its applications. In Proc. Comp. Sci.
Symp. in Russia (CSR’17), pp. 294–307. Springer, 2017. [doi:10.1007/978-3-319-58747-9_26,
ECCC:TR16-202] 2, 10
[15] Leslie G. Valiant: Short monotone formulae for the majority function. J. Algorithms,
5(3):363–366, 1984. [doi:10.1016/0196-6774(84)90016-6] 2
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 32
M ULTIPARTY K ARCHMER –W IGDERSON G AMES AND T HRESHOLD C IRCUITS
AUTHORS
Alexander Kozachinskiy
Scientific Researcher
Department of Mathematical Logic
Steklov Mathematical Institute
Moscow, Russia
kozlach mail.ru
https://kozlachinskiy.github.io/
Vladimir Podolskii
Leading Scientific Researcher
Steklov Mathematical Institute and
HSE University
Moscow, Russia
podolskii.vv gmail com
https://homepage.mi-ras.ru/~podolskii/
ABOUT THE AUTHORS
Alexander Kozachinskiy grew up in Moscow. For about 10 years, he was at the
Moscow State University, first as an undergraduate, and then as a Ph. D. student
advised by Nikolay Vereshchagin. He defended his thesis titled “Comparison of
Communication, Information and Decision Tree Complexities” in 2019. Currently
he works as a research fellow at the Steklov Mathematical Institute. He likes
to invent algorithms in areas like Circuit Complexity, where people are mostly
interested in lower bounds. Besides complexity, he works on Graph Games.
Vladimir Podolskii is a leading scientific researcher at the Steklov Mathematical
Institute. He also holds a part-time position at HSE University. His main research
interests are computational complexity, tropical algebra and logical foundations
of computer science. He graduated from Moscow State University in 2009,
advised by Nikolay Vereshchagin (and earlier by Alexander Razborov).
T HEORY OF C OMPUTING, Volume 18 (15), 2022, pp. 1–33 33