Christoph Meinel, Stephan Waack

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 >>>

Vince Grolmusz

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 >>>

Christoph Meinel, Stephan Waack

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 >>>

Pavel Hrubes, Pavel Pudlak

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 >>>