Probabilistic communication complexity over the reals

DOI10.1007/S00037-008-0255-ZMaRDI QIDQ2269005zbMATH OpenOpenAlexFDO

Authors Dima Grigoriev

Publication date 15 March 2010

Published in Computational Complexity (Search for Journal in Brave)

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)

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.

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

Cited in

(5)

• 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
• The Communication Complexity of Non-signaling Distributions
• Probabilistic communication complexity
• The communication complexity of pointer chasing: applications of entropy and sampling

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)