Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On total communication complexity of collapsing protocols for pointer
  jumping problem   This paper focuses on bounding the total communication complexity of
collapsing protocols for multiparty pointer jumping problem ($MPJ_k^n$). Brody
and Chakrabati in \cite{bc08} proved that in such setting one of the players
must communicate at least $n - 0.5\log{n}$ bits. Liang in \cite{liang} has
shown protocol matching this lower bound on maximum complexity. His protocol,
however, was behaving worse than the trivial one in terms of total complexity
(number of bits sent by all players). He conjectured that achieving total
complexity better then the trivial one is impossible. In this paper we prove
this conjecture. Namely, we show that for a collapsing protocol for $MPJ_k^n$,
the total communication complexity is at least $n-2$ which closes the gap
between lower and upper bound for total complexity of $MPJ_k^n$ in collapsing
setting.

2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
26
The categories of this paper are: bayes-an
31
The categories of this paper are: ao-sci
24
The categories of this paper are: dg-ga
32
The categories of this paper are: atom-ph
29
The categories of this paper are: funct-an
7
The categories of this paper are: hep-th
11
The categories of this paper are: hep-lat
6
The categories of this paper are: astro-ph
4
The categories of this paper are: cond-mat
22
The categories of this paper are: chao-dyn
36
The categories of this paper are: cmp-lg
0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
3
The categories of this paper are: physics