Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTIPARTITION COMMUNICATION COMPLEXITY:
Reports tagged with multipartition communication complexity:
TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

#### On Multipartition Communication Complexity

We study k-partition communication protocols, an extension
of the standard two-party best-partition model to k input partitions.
The main results are as follows.

1. A strong explicit hierarchy on the degree of
non-obliviousness is established by proving that,
using k+1 partitions instead of k may decrease
the communication complexity from ... more >>>

TR19-032 | 4th March 2019
Srikanth Srinivasan

#### Strongly Exponential Separation Between Monotone VP and Monotone VNP

We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$

more >>>

TR20-060 | 23rd April 2020
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

#### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in ... more >>>

TR20-073 | 5th May 2020
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

#### Lower Bounds on OBDD Proofs with Several Orders

This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>>

ISSN 1433-8092 | Imprint