Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity
Abstract
We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [2] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that for any deterministic decision tree complexity of a function can be lifted to the so called semi-structured communication complexity of , where is the Indexing gadget.
As our main contribution we extend these results to randomized setting. Our results also apply to a substantially larger set of gadgets. More specifically, we introduce a new complexity measure of gadgets, linear diversity. For all gadgets with non-trivial linear diversity we show that randomized decision tree complexity of lifts to randomized semi-structured communication complexity of . In particular, this gives tight lifting results for Indexing gadget , Inner Product gadget for all , and for Majority gadget for all . We prove the same results for deterministic case.
From our result it immediately follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [6] for Inner Product gadget.
To obtain our results we introduce a new secret sets approach to simulation of semi-structured communication protocols by decision trees. It allows us to simulate (restricted classes of) communication protocols on truly uniform distribution of inputs.
Keywords and phrases:
communication complexity, decision trees, liftingCopyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Communication complexity ; Theory of computation Oracles and decision treesEditors:
Raghu MekaSeries and Publisher:

1 Introduction
In recent years numerous results emerged that lift the complexity of a function in a weak model of computation to the complexity of a modified version of the function in a stronger model of computation [10, 13, 5, 11, 4, 14]. These results proved to be extremely useful for solving open problems in various areas of computational complexity [17, 18, 16, 9, 8]. In this type of results we start with a function that is hard for a weak computation model (like decision trees) and for a gadget we consider a function in which we substitute each variable of by an output of applied to fresh variables. Our goal is to show that the resulting function is hard for a strong computation model (like communication complexity or Boolean formula complexity). We would like the result to hold for as simple , as possible.
In this paper we are mostly interested in lifting from decision tree complexity to communication complexity, which is sometimes called query-to-communication lifting. This particular type of lifting has seen numerous results [17, 10, 12, 5, 11, 4]. In these papers the results of this type were obtained and gradually improved for both deterministic and randomized cases and for gradually increasing set of possible gadgets. The size of the gadget is a parameter that is of importance for applications. The smallest known size of the gadget for both deterministic and randomized case is logarithmic. For deterministic case, the results for logarithmic size of gadgets were obtained in [5] and [20]. For randomized case, the first result was obtained in [11] with a gadget of polynomial size. The paper [4] reduced the size of gadget for randomized case to logarithm. Obtaining the lifting results with the gadgets of constant size remains a major open problem.
One of the possible approaches to this problem is to address lifting to restricted models of communication or even simpler computational models and to try to obtain lifting with constant-size gadget in this setting. Some progress in this direction was obtained in recent independent papers [2, 6].
The paper [6] shows lifting from deterministic decision tree complexity to deterministic parity decision tree complexity for a wide range of gadgets , including gadgets of constant size. More specifically, for each gadget they introduce a stifling complexity measure and they show that . In particular, from their result it follows that and for any positive , where and are Indexing and Inner Product gadgets that are among the most standard in this field (see Subsection 2.3 for the definition of these functions).
The paper [2] introduces semi-structured communication complexity. In this model one of the players is allowed to send only parities of their input bits. This model is restricted compared to regular communication complexity model, but is more powerful (up to a factor of 2) compared to parity decision trees, as players can easily simulate a parity decision tree with a semi-structured communication protocol. The paper [2] shows lifting from deterministic decision trees to semi-structured communication protocol with gadget for any .
Our results
We show that for a wide range of gadgets (including constant size) lifting is possible from randomized decision trees to randomized semi-structured communication complexity.
More specifically, we introduce a complexity measure linear diversity for gadgets. Informally, it is equal to the number of distinct (up to negation) non-constant linear functions (over ) in Bob’s variables we can obtain by fixing Alice’s variables. We observe that the linear diversity of is and the linear diversity of is .
We show that for any function (or relation) for any and for any gadget with linear diversity randomized semi-structured communication complexity of is greater or equal to , where by we denote the minimal depth of probabilistic decision tree computing . In particular, our result applies to gadgets of constant size. Our result gives tight bounds for both and gadgets. When lifting to probabilistic parity decision trees, our result also gives tight bounds for the gadget using a trick described in Subsection 3.4.
Similarly to [6] we extend our result to give the same lower bound for the logarithm of the size of the randomized semi-structured communication protocol and to a version of communication complexity, in which Bob is allowed to send indicator functions of subspaces of his input bits.
Although our techniques (see below) is designed specifically for randomized case, we translate our results to deterministic case as well. Compared to [2] the deterministic version of our results apply to a wide range of gadgets.
As an immediate corollary, we have the same results (both randomized and deterministic) for lifting to parity decision trees. Compared to [6] the deterministic version of our result for parity decision trees uses linear diversity complexity measure instead of stifling. We discuss the comparison between these two measures below.
Our results can be used to obtain lower bounds on randomized parity decision tree complexity of Boolean functions. We provide a couple of examples of bounds we can obtain.
Linear diversity vs. stifling
A function is -stifled if for any subset of input variables and any bit we can fix all other variables in such a way that evaluates to no matter what the values of the variables in the subset are.
The binary logarithm of linear diversity measure is greater than stifling at least for some functions. A notable example is function that is a common gadget in lifting results. Its linear diversity is maximal, but its stifling is just 1.
Our techniques
The proof of our results builds on so-called simulation argument in the style of [11, 4]. In this argument, given a randomized communication protocol computing of cost , we build a randomized decision tree computing of depth . The tree simulates , querying the necessary information. Next we describe the simulation argument and then explain the new ideas.
For convenience we introduce the following notations:
-
The gadget: it is convenient to consider gadgets of the form , where corresponds to the inputs of Alice and corresponds to the inputs of Bob, and the linear diversity of is ; that is, for convenience, we assume that for any fixed first input of the resulting function on the second input is linear.
-
The collection of all gadgets: .
-
The input to the -th gadget: .
-
The whole inputs of Alice and Bob: , .
Simulation argument.
The main idea is that on input simulates on a random input that is distributed uniformly on . Since , will output as long as the simulation of performed correctly.
The main difficulty in this approach is to simulate on without knowing . To overcome this problem, it was shown in [11, 4] that the distribution does not differ substantially (from the perspective of the players) from the uniform distribution on all inputs. Thus, the tree can instead simulate on , where is distributed uniformly on , until reveals too much information about some block of inputs . Once this happens for some , the tree queries and proceeds with the simulation knowing the correct distribution of the pair .
However, in this approach the simulation becomes approximate. To be able to assume that the uniform distribution on does not differ too much from the uniform distribution on all inputs, we need that the size of the gadget is at least logarithmic in (we need this to bound the error probability of the simulation). Thus, it is not clear how to use this approach for gadgets of smaller size.
The key idea of our approach is to simulate precisely on the distribution . This allows us to work with the gadgets of constant size. To address the issue of the simulation with unknown , we introduce the main key ingredient of our argument, the secret sets technique.
Secret sets.
Let be some subset of . Assume for now that equals the XOR of variables of on the positions in . Then we can show that as long as is not in a linear span of linear functions sent by Bob in , the uniform distribution on is indistinguishable (by players) from the uniform distribution on the whole -th block of input. This allows us to simulate as if is known. Once falls into a linear span of functions sent by Bob, we just query and proceed with the simulation. To prove our bound, we must show that Bob needs to send many (about ) messages in on average to force us to query . Recall that is actually random. The intuition is that Bob must send roughly linear functions for their linear span to capture a random .
There are two key ingredients to actually prove that the secret set technique forces Bob to send many messages. Below is the brief description of them.
Narrowing Bob’s messages to blocks.
For each Bob’s message we assign a block which will account for it. For each message assigned in block , we remove the part of it that lies outside of . Denote by this set of truncated messages that assigned to th block.
Each will admit the following property. is not lying in the linear span of messages sent by Bob as long as it is not lying in the linear span of . At some point, the property can become violated after Bob sends a message, but we will send additional messages for Alice and Bob to restore the property. More precisely, we pick a linear combination of messages assigned to th block that annulates . We subtract from this linear combination, in which we take untruncated messages, and send this new message for Bob recursively.
Entropy.
We use the idea of fixed/unfixed blocks that was also used in the previous lifting theorems that utilized entropy. At the beginning, we consider all to be unfixed. Note that, initially, the binary entropy of is , since is uniformly distributed on . We want to show that rarely lies in the linear span of when a new element is added to . The case when the entropy of is sufficiently larger than is favorable for us, since in this case does not lie in the linear span of with a high probability. When the entropy of goes below that level, we fix (Alice sends ). Since Alice and Bob must send a lot of messages to decrease the entropy of below the desired level or to increase the size of , the number of fixed is low.
As another feature of our approach we would like to mention that unlike the previous papers our simulation algorithm has a very simple description: we fix Alice’s input randomly and maintain the linear space generated by Bob’s messages to decide on querying s. Correctness of the algorithm easily follows from its description and the most technical part of the proof shifts to the complexity analysis.
Organization
The rest of the paper is organized as follows. In Section 2 we give the necessary preliminary information and introduce key notions and notation. In Section 3 we give a formulation our results. In Subsection 3.5 we show some applications of our results. In Section 4 we introduce additional notation that is used in the proofs. In Subsection 5.1 we begin the proof of our main result and as a first step reformulate the theorem in the form that is convenient for the proof. In Subsection 5.2 we describe the protocol to simulate communication protocol by decision tree. In Subsection 5.3 we proof correctness of the simulation. In Subsection 5.4 we prove the bound on the number of queries in the simulation (this is the most technically heavy part of the proof).
Proofs of the remaining theorems are omitted due to the space constraint and are provided in the full version of the paper. The proofs of our results on lifting to the size of the communication protocols and to the subspace queries are achieved by a slight modification of the proof for the depth complexity. The proof of our results for the deterministic case are similar to the ones for randomized setting with necessary technical modifications.
2 Preliminaries
2.1 Standard Notation
Here we will describe some notation that we use. We denote for a non-negative integer . The addition mod 2 is denoted by XOR or . Sometimes, we view as a vector space .
2.2 Computational Models
For functions of the form we consider semi-structured communication protocols introduced in [2]. In these protocols Bob is only allowed to send the XOR of some subset of his input bits (and Alice is not restricted). A randomized semi-structured protocol is just a distribution over deterministic semi-structured protocols. We say that such a protocol computes the function correctly, if on every input the probability of the correct output is at least . The complexity of in this model is the minimal depth of a protocol computing .
We also consider a subspace-query model. Consider communication protocols in which Bob is only allowed to send indicators of whether his input lies in an affine subspace of . We denote by the minimum complexity of a randomized protocol computing , where the protocol is taken from the restricted class.
Additionally, let us introduce a size-complexity of a protocol. A deterministic communication protocol can be represented by a tree in which in every node either Alice or Bob sends a message. We call the size-complexity of the protocol to be the number of leafs in this tree. Denote by the minimum size-complexity of a randomized semi-structured protocol computing .
We denote by , and the deterministic versions of these complexity measures.
We can define the semi-structured complexity measures for relations completely analogously. Here a deterministic protocol is said to compute if for any it outputs any such that , if there is such (the protocol can give any output if there is no such ).
For a function we denote by the minimal depth of a decision tree computing . We denote by the minimal depth of a parity decision tree computing (on each step such a decision tree can query an XOR of a subset of the input bits). Analogously to semi-structured communication complexity, we denote by , , , , and complexity measures defined by deterministic and randomized parity decision trees.
There is the following standard connection between parity decision trees and communication complexity protocols.
Lemma 1.
For any function we have
Proof.
Given a (randomized) parity decision tree for Alice and Bob can use it to compute the function by a (randomized) communication protocol. For this they simulate each query one by one computing XOR of their portion of the input and sending them to each other. Simulation of each query requires two bits of communication.
2.3 Gadgets
We first define a class of gadgets that is of use for us.
Definition 2 (Family of linear functions).
The gadget is a family of linear functions of order , if the following is true
-
(1)
is a non-trivial linear function as a function of the second argument (that is, it is an XOR of a nonempty subset of its inputs),
-
(2)
.
For convenience from now on we will use the notation .
We will use the following notion of gadget reduction.
Definition 3 (Gadget reduction).
Consider two gadgets . Then is reducible to , if there are mappings , such that
-
(1)
-
(2)
is linear, that is
Note that gadget reduction relation is transitive.
Gadget reduction is useful for us due to the following lemma.
Lemma 4.
Assume that a gadget reduces to a gadget . Then for any relation we have
The same inequalities are true for the deterministic complexities.
Proof.
If Alice and Bob would like to compute , they can just compute the mappings on their inputs individually and use the protocol for . Since is linear, Bob can simulate the protocol for sending only XORs of his input bits. To see that, denote by . Thus, is uniquely determined by . Let be Bob’s input, and let . An arbitrary parity message of can be represented as for some . Here, is the dot product modulo 2. Observe that . In other words, to compute , it is enough to take the XOR of all those for which equals one. This means that Bob can translate parity messages of to parity messages of .
Next we define the main complexity measure for the gadgets.
Definition 5 (Linear diversity).
We let linear diversity of a function be the maximal such that there is a family of linear functions of order such that reduces to .
Next we introduce a couple of standard gadgets that will be important for us.
Definition 6 (Index function).
Let be the function that on input outputs .
Definition 7 (Inner product function).
Let be the function that on input outputs .
Lemma 8.
is a family of linear functions of order . has linear diversity .
Proof.
The statement of the lemma is almost immediate. For , note that for any the output of is , which is a linear function. For , note that for any fixed the output of is , which is a non-trivial linear function for each . The reduction from a family of linear functions is trivial ( is an identity function and sends an integer to its binary representation).
Lemma 9.
With probability approaching as tends to infinity, a random gadget has linear diversity at least . (The values of on each input are chosen randomly and independently.)
The proof of this lemma can be found in the full version of the paper.
3 Results Statement
3.1 Randomized Semi-Structured protocols
Theorem 10.
Let be a family of linear functions of order . Then for any relation we have
We note that big- part is trivial, since Alice and Bob in communication protocol can simulate a decision tree for and spend bits of communication for each tree query to compute the function on the corresponding inputs.
We prove the following stronger versions of Theorem 10.
Theorem 11.
Let be a family of linear functions of order . Then for any relation we have
Theorem 12.
Let be a family of linear functions of order . Then for any relation we have
For both theorems big-O part follows since and for any function .
As a corollary of these theorems and 4 we immediately obtain the following.
Corollary 13.
Let have linear diversity at least for . Then for any relation we have
The same result is true for and .
3.2 Deterministic Semi-structured protocols
We translate our results to deterministic case as well.
Theorem 14.
Let be a family of linear functions of order . Then for any relation we have
Corollary 15.
Let have linear diversity at least for . Then for any relation we have
The same result is true for and .
3.3 Parity decision trees
Finally, we prove that our results imply the same results for parity decision trees instead of semi-structured communication protocols.
Theorem 16.
Let have linear diversity at least for . Then for any relation we have
The same is true for and . The same results are also true for the deterministic complexities.
The part of this theorem concerning is a direct consequence of 1, Theorem 10, and 4. The same applies to .
The part of this theorem about and does not follow from previous theorems that easily, and we prove them in the full version of the paper.
3.4 More powerful gadget reduction
In this section, we describe a more general version of a gadget reduction than in 3. We apply the reduction to the MAJ gadget, obtaining tight bounds for lifting to parity decision trees.
More specifically, we can consider the domain of a gadget as a vector space and input variables as coordinates in the standard basis. The idea is that we can switch to another basis in this vector space, consider new coordinates as variables and apply the reduction in 3 after that. Since the transformation to the new variables is linear, new variables can be expressed as an XOR of old variables and vice versa. Thus, the parity decision trees in new and old variables can simulate each other (this does not hold for communication complexity setting, since switching to the new basis mixes up the variables belonging to Alice and Bob).
We illustrate this idea on a MAJ gadget. Recall that is a function that returns iff at least of its variables are equal to .
Lemma 17.
For any relation and , .
This method can be applied to gadgets other than MAJ. We formulate this approach in a theorem.
Theorem 18.
Let , , – be functions such that linear diversity of is at least . Suppose that reduces to after a change of basis. Then, for any relation ,
Proofs of these results are provided in the full version of the paper.
3.5 Applications
A more detailed description of applications can be found in the full version of the paper.
Recursive majority function
Let be the majority function that returns if at least two of its three input bits equal to , otherwise it returns .
For , define to be in which each argument is substituted by . Thus, takes inputs.
In [15], it is shown that
It is easily observed that is at least linear diverse. By using it as a gadget, our lifting theorem imply that . Thus, parity queries do not help in computing as compared to single variable queries.
The same approach can be applied to formulas having the form of complete binary AND-OR-tree. In other words, this function is obtained by repeated iteration of . It was shown in [19] that of this function is at least , where is the number of inputs. Since can be used as a gadget, we translate this result to parity decision trees.
Quantum Complexity
Our lifting theorem can be applied to exhibit a separation between randomized parity decision tree complexity and bounded-error quantum complexity. Let . It was shown in [1] that there is a versus separation between the quantum and randomized query complexity. The separation was shown for a partial function called -fold Forrelation.
Using our result, we can lift this separation to randomized parity query complexity. Consider the function . On the one hand, its quantum complexity is the same as the quantum complexity of (up to a factor), since a quantum protocol can extract inputs to from in constant number of additional queries. On the other hand, by Theorem 10, the randomized parity query complexity of is no less than its randomized query complexity. Hence, we obtain the same separation even if our query model can ask parity queries.
An alternative method to obtain separation between randomized parity query and quantum complexity was given in [3]. They also relied on the result of [1]. They used Fourier analysis and properties of -Fold Forrelation to derive their result. In contrast, our lifting theorem can lift any function that exhibits the separation.
4 Notation for proving main theorems
In this section we introduce notation and facts about entropy that will be used for proving the main theorems in the subsequent sections. Recall that in a semi-structured communication protocol, Bob can send only parities of its input. In a lifting setting, Bob is given boolean variables. For each of variables of the initial function, there are gadget’s variables. To analyze Bob’s messages, we introduce the following definitions.
4.1 Notation
Definition 19 (XOR of a subset).
For a set and , we define
Analogously, we define if and .
If is the Bob’s input, then each of his messages can be represented as for some .
Definition 20 (Subsets of as a linear space).
We view subsets of as vectors in a linear space over (where addition (+) corresponds to symmetric difference).
With this notation, for any , .
Definition 21 (Linear Order on ).
We introduce a lexicographic linear order on . A pair is said to be lower than if or .
Definition 22 (Principal variable of a non-empty subset).
For a non-empty set , denote by its lowest element.
Definition 23 (Block).
We refer to as -th block. A non-empty subset touches -th block if .
Definition 24 (Bernoulli distribution).
Denote by Bern(p) a distribution of a random variable that takes value with probability and with probability .
Definition 25 (Entropy).
For a random variable , denote by its binary entropy. If is a set, then we define its entropy as . If is a number, then denotes the binary entropy of the distribution .
Recall that the binary entropy of a random variable taking values with non-zero probabilities equals to
4.2 Entropy theorems
We state well-known results that will be used for proving our main theorems.
Lemma 26 (Gibbs’ inequality [7]).
Let . Then,
Lemma 27 (Fano’s Inequality [7]).
Let be random variables. Let . Then,
where denotes the support of .
5 Proof of Theorem 10
5.1 Reformulation of Theorem 10
As we noted in Section 3, the -direction is simple. Thus, it remains to prove the other direction.
Let be a randomized semi-structured protocol computing . Denote by the depth of . Our goal is to construct a randomized tree of depth , that computes for any given .
The idea is to simulate on a randomly uniformly chosen pair satisfying . For convenience, denote . For any pair we have that with probability at least . Thus, if we sample , the protocol will also be equal to with probability at least .
We use the following general strategy for : sample , sample (recall that is a random distribution on deterministic protocols), and output . Note that the choice of the pair is independent from the choice of , and thus it does not matter in which order we sample and . As a result, what is left to do is to simulate the given deterministic semi-structured protocol on a random pair .
We are going to prove the following intermediate theorem.
Theorem 28.
Let be a deterministic semi-structured protocol with inputs from . Let be equal to the depth of . Then, there exists a randomized decision tree which, on input , outputs a random variable that is destributed as for . The expected number of queries to made by is , where the expectation is taken over for a fixed .
Before proceeding to the proof of Theorem 28 we show how to prove Theorem 10 based on Theorem 28.
Proof of Theorem 10.
The computation of on input proceeds as follows. We choose a random and run provided by Theorem 28 on input . By definition, has the same distribution as for . Thus, computes with probability at least .
The average number of queries made by is at most . To achieve this number of queries in the worst case, we halt if it makes 10 times more queries than the expected number. By Markov’s inequality, this only happens with probability at most , the probability of the correct answer is still a constant greater than and it can be increased to by the standard argument for error reduction.
Now we proceed to the proof of Theorem 28. For this we need to describe how simulates . In the subsequent sections we will heavily use the notation introduced in Section 4.
5.2 Simulation algorithm for
In this section we describe the algorithm for .
starts by sampling a random and assuming that .
After that, starts the simulation of . Since is fixed ( knows but for it is a random variable), Alice’s messages are easily simulated. Next, we describe how simulates Bob’s parity messages on the (unknown) variables .
Recall that we can view as a family of linear functions of order (one function for each value of ). Since are linear functions, we can represent them as for some .
Let . Note that all s are linearly independent since they are in distinct blocks. From now on we will call the secret sets.
Consider an arbitrary step of simulation and assume Bob has already sent the parities of his inputs for the sets and is now supposed to send the parity of ’s in the set . Note, that it can be assumed that is linearly independent of : otherwise, the message does not reveal any new information and can be omitted from the protocol. There are two cases:
-
(1)
There is a linear combination of s that includes and equals to some linear combination of the secret sets:
In this case, the value is uniquely determined since
The ’s parities on the sets are already known from the previous messages of Bob. Therefore, queries (if it hasn’t already), and we calculate the value that Bob sends in this vertex.
-
(2)
Such a linear combination does not exist. In this case, sends a random bit as an XOR of on the set . In terms of the protocol , this corresponds to proceeding to one of the left and right children with equal probabilities.
Thus, we have described how to simulate each Bob’s message. Once reaches a leaf of , it outputs the value written in this leaf.
5.3 Correctness of the simulation of done by
Next, we need to show that indeed simulates on a random pair , and that makes queries on average. We start with the correctness of the simulation.
It is easy to see that for any the projection of onto is the uniform distribution on , therefore fixing correctly corresponds to the distribution of we would like to simulate the protocol on.
Note that once is fixed the only constraints on are of the form , where . In particular, any variable in , not included in , has a distribution.
Next, we justify why the algorithm can send as an XOR of if no linear combination exists (Case 2 above). Indeed, the ’s parities of define an affine subspace in our linear space. Since is linearly independent of , each of the conditions and is satisfied by exactly half of the points of the affine subspace.
If there exists a linear combination of s that includes and equals a linear combination of s (Case 1 above), then given the previous messages and the value of there is only one possible value for , which indeed sends in our simulation.
Thus, the distribution of matches for .
5.4 Upper bound on the average number of queries made by
Next we show that makes queries to the variables on average. For this we introduce some complexity measures and study their behaviour during the execution of the protocol. To make this analysis cleaner we first modify the protocol to add more messages to it. This does not change the output of the protocol, but it allows us to simplify the exposition of time analysis. In the next section we describe the modified protocol. Next we discuss its connection to . Finally, in Subsubsection 5.4.3, we derive the upper bound on the number of queries made by .
Since we need to show the upper bound on the number of queries of for any , we fix for the whole argument.
5.4.1 Description of the modified protocol
Here we describe , a refined version of . Note that the protocol depends on , which is fixed throughout the whole argument. We will be interested only in the behaviour of the protocol on inputs in .
We modify the protocol in two ways. First, we modify the messages sent by Bob into equivalent messages. This does not actually change the information transmitted by Bob, this modification is needed only for the purpose of the analysis of the protocol. Next, at some moments of time we add additional messages sent by the players. The information transmitted in these messages is not affecting the following messages in the protocol. One can think of this in the following way: at some points of the protocol the players pause the execution of the protocol, exchange some extra information, and then resume the execution of the protocol as if nothing happened. These extra messages are needed just to introduce new intermediate vertices in communication tree that will allow us to analyse the complexity of in a cleaner way.
The pseudocode for the algorithm is provided in Figure 1. Next we describe the protocol and introduce some important notation related to it.
First of all, observe that if Bob sends , as parities on the sets respectively, this is equivalent to sending , as parities on respectively. More generally, applying an invertible linear transformation to Bob’s messages does not change the information transmitted.
Recall that by we denote the secret sets. Note that depends on and, thus, initially is only known to Alice. Initially, all are unrevealed, and over the course of the simulation, they will be gradually revealed. We also introduce a separate notion that of being fixed. Initially, all are unfixed and then will change status to fixed over the course of the simulation. A revealed will also be fixed, but not necessarily vice versa.
Suppose that at the current moment of simulating , Bob has sent parities on the sets and now he wants to send the parity on the set . We will maintain the principle variable invariant: all are distinct and, if , then is lower than . The variables will be referred to as principal. In particular, from this invariant, it follows that are linearly independent.
Define the procedure sift, which will transform to an equivalent message. The procedure sift iterates over and replaces with if . Note that after this procedure for any we have that .
We run the procedure sift on . If it turns into an empty set, then Bob’s message does not provide any new information. In this case we finish its processing and move on to further simulation of . If the resulting is not empty, then it contains a principal variable. Since after sift, does not contain principal variables of previous messages, the principal variable of does not coincide with the principal variable of previous messages. We insert a copy of into the sequence in such a way that the principle variable invariant is maintained. That is, now the length of the sequence is . Assume that is in the -th input block. Let . In other words, we consider all sets whose principal variables are in the -th block and intersect them with the -th block. Note that sets in are linearly independent. Denote by the linear span of with the zero vector (empty set) removed.
At this point, we apply the second modification to the protocol. If the binary entropy of is less than , Alice sends , and is considered fixed. Here the protocol views to be a random variable of the distribution conditioned on the information about that the protocol has learnt so far. Note that we fixed in advance, and we assume that the inputs given to the players are indeed in (we are not interested in the behaviour of the protocol on other inputs). As a result, both players can compute the entropy of and compare it to without communication.
After that Alice sends a message indicating if lies in 111Note that this might be redundant if we just communicated the whole . We choose to keep this step even if it is redundant to make the pseudocode in Figure 1. In the analysis below the redundancy of these messages is reflected in 35.. If this is not the case or if has already been revealed on one of the previous steps, we finish processing the message and proceed with the further simulation of the protocol . If lies in , then we consider to be revealed. In this case Alice sends , and we fix if it was not already fixed before. Bob sends . Next, let be the sets whose linear combination, when intersected with the -th block, equals the secret set . The set must be present among them: otherwise, would have been revealed at an earlier step. Without loss of generality we can assume that . We update to and perform the same procedure with the updated starting with sift (note that from this players can compute for the new without additional communication since is known). Note, that during this iteration we removed from all elements in the -th block without introducing anything to in the previous blocks (all sets in the combinations had their principle variables in the -th block). As a result, the updated lies within the blocks that are higher than -th block and the whole procedure of updating will be finished eventually.
Refined protocol on input :
5.4.2 Connection between and
The protocol is useful for upper bounding the complexity of due to the following lemmas.
Lemma 29.
The following is a while-loop invariant in : If a linear combination of equals a linear combination of , then all s in this linear combination are revealed.
Proof.
First note that for all such that is unrevealed, does not lie in . Otherwise, at the line of the algorithm, would have been revealed.
Assume that this invariant is violated. Let this linear combination be , where . If there are many linear combinations that violate invariant, then choose the one with the greatest . Let be the block of the variable . Then, must be equal to , since . It follows that must be revealed, since it lies in . At the line 28 of the algorithm, it is ensured that a linear combination is added to the set of s. is contained in blocks strictly higher than -th block and, by assumption, is equal to a linear combination of containing an unrevealed secret set. Therefore, we obtained a contradiction with the maximality of .
Next we establish the connection between and . By construction, simulates on a random input . Fix to be the outcome of the random bits of the tree . Then will simulate on some pair .
We show the following.
Lemma 30.
The number of queries to made by is less or equal than the number of revealed sets in protocol on input .
Proof.
By definition of , it queries only if there is some linear combination of containing that equals a linear combination of . By 29, we get that is queried by only if is revealed. Hence, the statement of the lemma follows.
The lemma holds for all . In particular, if we average over , then we get that the expected number of queries made by is bounded by the expected number of revealed sets in protocol on a random . Therefore, it remains to obtain an upper bound on the expected number of revealed sets.
5.4.3 Upper bound on the expected number of revealed sets in
For each vertex of the protocol , define
In other words, if is the rectangle corresponding to the vertex in the protocol , then .
Essentially, if the protocol has reached the vertex , then can be any element of the set . Now consider the uniform distribution and run on a random pair from this distribution. Then is precisely the conditional distribution of the pair , given that has reached . In what follows, we consider . We will be interested in the entropy of the projection of this distribution onto , hence we introduce the following notation
Let be the secret set in the -th block. The set depends on and, moreover, there is a one-to-one correspondence between s and s. Therefore, their entropies are equal: . Denote by the set corresponding to the vertex , and by its linear span with the zero vector removed. That is, .
Using Fano’s inequality, we can show the following.
Lemma 31.
Let be a vertex of the protocol in which Alice sends a message revealing whether lies in the linear span (this is (A2) type of message on Figure 1). Then, if , then does not lie in with probability at least .
Proof.
Define to be equal to if , and to be equal to any element in otherwise. Note that with this definition, . Denote this probability by . Then, by Fano’s inequality we have
Assume that . Then
Since , we get at a contradiction with the statement of the lemma.
Now let’s show that if at vertex Alice or Bob sends one-bit message, then the entropy on average does not decrease significantly.
Lemma 32.
Let denote the bit of information that Alice or Bob sends at vertex . Then
Proof.
We have that
and
In other words, the entropy of the distribution of drops by no more than on average on one step of the protocol. Next, we introduce the deficiency of the distribution. Let
and let the deficiency be
Note that if is fixed. Thus, for any , as . We will omit the superscript if the vertex is clear from the context.
Now we consider and introduce some random variables for various types of messages of on the input .
For this we consider a finer classification of the messages sent by Alice, compared to the one in Figure 1:
- (A1)
-
A message that Alice sends in .
- (A2’)
-
A message , such that we have before sending this message. In other words, in these messages was not previously fixed.
- (A2”)
-
A message , such that we have before sending this message. In other words, in these messages was previously fixed.
- (A3’)
-
A message that Alice sends to find out the exact value of , and was not fixed before sending this message.
- (A3”)
-
Same as (A3’) but was fixed before sending this message.
For Bob we use the same classification of messages as in Figure 1:
- (B1)
-
A message that Bob sends in .
- (B2)
-
A message in which Bob communicates the value
Let denote the number of messages of the corresponding type sent by the protocol during the whole computation. All of these are random variables depending on , which we draw randomly: .
The following inequality hold.
Observation 33.
.
Proof.
When Alice sends a message of type (A2’), by 31 the secret set does not lie in with probability at least . If it does not lie in , the processing of the Bob’s message is over. Thus, for each query of type (B1), there will be no more than queries of type (A2’) on average.
Observation 34.
At the end of the computation, the number of fixed is greater or equal than . In particular, there are at least coordinates such that decreased from to . During each of these decreases of s, decreases by at least on average.
Proof.
By definition, is precisely equal to the number of the fixed secret sets . When the status of changes from unfixed to fixed, drops from to . Since changes to only when becomes less than (as ensured by if’s on lines and ), sending transmits no more than information. Thus, we get the required decrease of by at least on average.
Observation 35.
Messages of types (B2), (A2”), and (A3”) do not affect .
Proof.
A message of the type (B2) does not change since pairs have a property that . Thus, message does not decrease the entropy of the distribution.
Just before a message of type (A2”) is sent, by definition, we have that . But in lines it is ensured that if is lower than this threshold, then will be fixed. Thus, is not only lower than , but also equals to . Thus, does not influence .
By definition, is fixed before sending a message of type (A3”). Thus, and sending does not reveal any information.
Observation 36.
At the end of the protocol’s execution, .
Proof.
A new set is generated and added to the list of s either when a message of type (B1) is sent, or after a message of type (B2) is sent.
Let’s show how the desired bound follows from these lemmas. Note that if is revealed, then it must be fixed. As a consequence, we get since equals the number of revealed sets and equals the number of fixed ones. Our goal is to upper bound the number of revealed sets. Thus, we only need to upper bound by , as is exactly the number of messages sent by the protocol .
Lemma 37.
Proof.
By 32 messages of type (A1) and (B1) increase by no more than on average. The same is true for messages of type (A2’). As a result, due to 34 and 35,
since is always greater or equal than than . Applying 33 and rearranging we get
Now we consider two cases.
-
1.
Note that . Using the fact that and the inequality above, we obtain
Since , we get .
-
2.
Note that if we are sending a message of type (A3’) and it is true that , then decreases by at least on average. The number of s such that does not exceed by 36. As a result,
Using , we get
Thus, we again obtain .
References
- [1] Nikhil Bansal and Makrand Sinha. k-forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1303–1316, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3406325.3451040.
- [2] Paul Beame and Sajin Koroth. On disperser/lifting properties of the index and inner-product functions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 14:1–14:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ITCS.2023.14.
- [3] Eric Blais, Li-Yang Tan, and Andrew Wan. An inequality for the Fourier spectrum of parity decision trees. CoRR, abs/1506.01055, 2015. arXiv:1506.01055.
- [4] Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM J. Comput., 50(1):171–210, 2021. doi:10.1137/19M1310153.
- [5] Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation theorems via pseudo-random properties. Comput. Complex., 28(4):617–659, 2019. doi:10.1007/S00037-019-00190-7.
- [6] Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. Lifting to parity decision trees via stifling. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 33:1–33:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ITCS.2023.33.
- [7] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, July 2006.
- [8] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1–30, 2020. doi:10.4086/TOC.2020.V016A013.
- [9] Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778–1806, 2018. doi:10.1137/16M1082007.
- [10] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435–2450, 2018. doi:10.1137/16M1059369.
- [11] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM J. Comput., 49(4), 2020. doi:10.1137/17M115339X.
- [12] Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208–217, 2018. doi:10.1137/17M1136869.
- [13] Bruno Loff and Sagnik Mukhopadhyay. Lifting theorems for equality. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 50:1–50:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.STACS.2019.50.
- [14] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 104:1–104:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ITCS.2022.104.
- [15] Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming, pages 317–329, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. doi:10.1007/978-3-642-22006-7_27.
- [16] Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1246–1255. ACM, 2017. doi:10.1145/3055399.3055478.
- [17] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Comb., 19(3):403–435, 1999. doi:10.1007/S004930050062.
- [18] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406–415. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.51.
- [19] Miklos Santha. On the Monte Carlo Boolean decision tree complexity of read-once formulae. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30 - July 3, 1991, pages 180–187. IEEE Computer Society, 1991. doi:10.1109/SCT.1991.160259.
- [20] Xiaodi Wu, Penghui Yao, and Henry S. Yuen. Raz-McKenzie simulation with the inner product gadget. Electron. Colloquium Comput. Complex., TR17-010, 2017. URL: https://eccc.weizmann.ac.il/report/2017/010.