Separating counting communication complexity classes

Damm, Carsten ; Krause, Matthias ; Meinel, Christoph ; Waack, Stephan

Document Type: Working paper
Year of publication: 1992
The title of a journal, publication series: Forschungsbericht / Universität Trier, Mathematik, Informatik
Volume: 92-01
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 0944-0488
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
Abstract: We develope new lower bound arguments on communication complexity and establish a number of separation results for Counting Communication Classes. In particular, it will be shown that for Communieation Complexity MOD p -P and MOD q -P are uncomparable via inclusion for all pairs of distinct primes p, q. Further we prove that the same is true for PP and MOD p -P for any prime number p. Our results are due to mathematical characterization of modular and probabilistic communication complexity by…

Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item