The communication-complexity equivalence conjecture for partition and exactness
The communication-complexity equivalence conjecture for partition and exactness
For positive integers and , let denote the problem of determining whether pairwise disjoint sets form a partition of , and let denote the corresponding problem of determining whether their union is exactly . Write for the deterministic -party number-on-the-forehead communication complexity of a function or problem . Partition–exactness conjecture.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.