The communication-complexity equivalence conjecture for partition and exactness

For positive integers nn and kk, let Partn,kPart_{n,k} denote the problem of determining whether pairwise disjoint sets S1,,SkS_1,\ldots,S_k form a partition of [n][n], and let Exactlyn,kExactly_{n,k} denote the corresponding problem of determining whether their union is exactly [n][n]. Write Dk(f)D_k(f) for the deterministic kk-party number-on-the-forehead communication complexity of a function or problem ff. Partition–exactness conjecture.

Dk(Partn,k)=Θ(Dk(Exactlyn,k)).D_k(Part_{n,k}) = \Theta(D_k(Exactly_{n,k})).

The conjecture expresses the expectation that verifying that pairwise disjoint sets form a partition has communication complexity of the same order as verifying exact coverage. The source presents this as an open question; no resolution is stated.

Sources & referencesView supporting material

Primary source

Adi Shraibman, “A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem”, arXiv:1706.02277 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.