English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper focuses on bounding the total communication complexity ofcollapsing protocols for multiparty pointer jumping problem ($MPJ_k^n$). Brodyand Chakrabati in \cite{bc08} proved that in such setting one of the playersmust communicate at least $n - 0.5\log{n}$ bits. Liang in \cite{liang} hasshown 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 totalcomplexity better then the trivial one is impossible. In this paper we provethis 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 gapbetween lower and upper bound for total complexity of $MPJ_k^n$ in collapsingsetting.

On total communication complexity of collapsing protocols for pointer jumping problem