Probabilistic communication complexity over the reals

DOI10.1007/S00037-008-0255-ZzbMATH Open1185.68880arXiv0710.2732OpenAlexW1637258132MaRDI QIDQ2269005FDOQ2269005

Dima Grigoriev

Publication date: 15 March 2010

Published in: Computational Complexity (Search for Journal in Brave)

Abstract: Deterministic and probabilistic communication protocols are introduced in which parties can exchange the values of polynomials (rather than bits in the usual setting). It is established a sharp lower bound $2n$ on the communication complexity of recognizing the $2n$-dimensional orthant, on the other hand the probabilistic communication complexity of its recognizing does not exceed 4. A polyhedron and a union of hyperplanes are constructed in $R{R}^{2n}$ for which a lower bound $n/2$ on the probabilistic communication complexity of recognizing each is proved. As a consequence this bound holds also for the EMPTINESS and the KNAPSACK problems.

Full work available at URL: https://arxiv.org/abs/0710.2732

zbMATH Keywords

EMPTINESSKNAPSACK problemsprobabilistic communication protocols

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cited In (4)

• The Communication Complexity of Non-signaling Distributions
• The communication complexity of pointer chasing: applications of entropy and sampling
• On Optimality in Probability and Almost Surely for Processes with a Communication Property. I. The Discrete Time Case
• Correlation in Hard Distributions in Communication Complexity

   Recommendations

• Probabilistic communication complexity 👍 👎
• The Probabilistic Communication Complexity of Set Intersection 👍 👎
• Lower bounds for one-way probabilistic communication complexity 👍 👎
• Communication complexity 👍 👎
• Fractional Covers and Communication Complexity 👍 👎

This page was built for publication: Probabilistic communication complexity over the reals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269005)