Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe layer complexity of Arthur-Merlin-like communication
193
0
0.0
(
0
)
Added by
Dmitry Gavinsky
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
D. Gavinsky
Ask ChatGPT about the research
No Arabic abstract
In communication complexity the Arthur-Merlin (AM) model is the most natural one that allows both randomness and non-determinism. Presently we do not have any super-logarithmic lower bound for the AM-complexity of an explicit function. Obtaining such a bound is a fundamental challenge to our understanding of communication phenomena. In this work we explore the gap between the known techniques and the complexity class AM. In the first part we define a new natural class Small-advantage Layered Arthur-Merlin (SLAM) that have the following properties: - SLAM is (strictly) included in AM and includes all previously known sub-AM classes with non-trivial lower bounds. - SLAM is qualitatively stronger than the union of those classes. - SLAM is a subject to the discrepancy bound: in particular, the inner product function does not have an efficient SLAM-protocol. Structurally this can be summarised as SBP $cup$ UAM $subset$ SLAM $subseteq$ AM $cap$ PP. In the second part we ask why proving a lower bound of $omega(sqrt n)$ on the MA-complexity of an explicit function seems to be difficult. Both of these results are related to the notion of layer complexity, which is, informally, the number of layers of non-determinism used by a protocol. We believe that further investigation of this concept may lead to better understanding of the communication model AM and to non-trivial lower bounds against it.
rate research
Read More
We study the communication complexity of computing functions $F:{0,1}^ntimes {0,1}^n rightarrow {0,1}$ in the memoryless communication model. Here, Alice is given $xin {0,1}^n$, Bob is given $yin {0,1}^n$ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS13), space bounded communication complexity by Brody et al. (ITCS13) and the overlay communication complexity by Papakonstantinou et al. (CCC14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least $c log n$? Note that $cgeq 2+varepsilon$ would imply a $Omega(n^{2+varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nev{c}iporuk in 1966.
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including $-$ most famously $-$ interactive randomised communication with bounded error, the problem requires much communication. In this work we were looking for a variation of the set disjointness problem, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection.
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $epsilon$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $tilde{O}(n/(tepsilon^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where three players receive integer inputs and need to decide if their inputs sum to a given integer $n$. There is a considerable body of literature dealing with the same problem, where $(mathbb{N},+)$ is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of work. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that appeal to recent advances in Additive Combinatorics and Ramsey theory. We reveal new and unexpected connections between the NOF communication complexity of high dimensional permutations and a variety of well known and thoroughly studied problems in combinatorics. Previous protocols for Exactly-n all rely on the construction of large sets of integers without a 3-term arithmetic progression. No direct algorithmic protocol was previously known for the problem, and we provide the first such algorithm. This suggests new ways to significantly improve the CFL protocol. Many new open questions are presented throughout.
The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to give good bounds, because the increment of the value of the game is linear (rather than exponential) in the number of communicated bits. We show in this paper the existence of XOR games where the discrepancy method yields bounds as poor as one desires. Indeed, we show the existence of such games with any previously prescribed value. To prove this result we apply the theory of p-summing operators, a central topic in Banach space theory. We show in the paper other applications of this theory to the study of the communication complexity of XOR games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
