Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with communication protocols:
TR94-022 | 12th December 1994
Christoph Meinel, Stephan Waack

The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

We prove that the modular communication complexity of the
undirected graph connectivity problem UCONN equals Theta(n),
in contrast to the well-known Theta(n*log n) bound in the
deterministic case, and to the Omega(n*loglog n) lower bound
in the nondeterministic case, recently proved by ... more >>>

TR95-046 | 4th August 1995
Vince Grolmusz

On the Power of Circuits with Gates of Low L_1 Norms

We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ... more >>>

TR96-017 | 19th February 1996
Christoph Meinel, Stephan Waack

The ``Log Rank'' Conjecture for Modular Communication Complexity

The ``log rank'' conjecture consists in the question how exact
the deterministic communication complexity of a problem can be
determinied in terms of algebraic invarants of the communication
matrix of this problem. In the following, we answer this question
in the context of modular communication complexity. ... more >>>

TR17-048 | 14th March 2017
Pavel Hrubes, Pavel Pudlak

A note on monotone real circuits

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

ISSN 1433-8092 | Imprint