2007/10/15 by Dima Grigoriev, Grigoriev, Dima
Computer Science · #68W40 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #cs.CC #msc:68W40
paper · pdf · doi:10.48550/arxiv.0710.2732
arxiv created 2007/10/15 · openalex publication_date 2007/10/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \RR2n 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.