Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-049 | 11th July 2001 00:00

On Multi-Partition Communication Complexity of Triangle-Freeness



We show that recognizing the $K_3$-freeness and $K_4$-freeness of
graphs is hard, respectively, for two-player nondeterministic
communication protocols with exponentially many partitions and for
nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to
Papadimitriou and Sipser, which says that for every balanced
red-blue coloring of the edges of the complete $n$-vertex graph
there is a set of $cn^2$ triangles, none of which is
monochromatic and no triangle can be formed by picking edges
from different triangles.

Using a probabilistic argument, we extend this lemma to the case
of exponentially many colorings as well as to partial colorings.


Comment #1 to TR01-049 | 25th July 2002 17:28

Triangle-Freeness is Also Hard for Read-r Times Branching Programs Comment on: TR01-049

Comment #1
Authors: Stasys Jukna
Accepted on: 25th July 2002 17:28
Downloads: 2103


In ECCC TR01-049 we have proved a truly exponential lower bound
on the size of r-n.b.p. (nondeterministic syntacticcread-r times
branching program) recognizing whether a given graph has no
4-clique. Here we note that, although not explicitely stated there,
the same argument implies a (not truly but still exponential)
lower bound also for r-b.p.'s recognizing the triangle-freeness
of graphs.

Comment #2 to TR01-049 | 11th December 2002 09:55

Comment #2
Authors: Jukna Stasys
Accepted on: 11th December 2002 09:55
Downloads: 1775


ISSN 1433-8092 | Imprint