ECCC-Report TR01-049https://eccc.weizmann.ac.il/report/2001/049Comments and Revisions published for TR01-049en-usWed, 11 Dec 2002 09:55:46 +0200
Comment 2
| |
Jukna Stasys
https://eccc.weizmann.ac.il/report/2001/049#comment2Wed, 11 Dec 2002 09:55:46 +0200https://eccc.weizmann.ac.il/report/2001/049#comment2
Comment 1
| Triangle-Freeness is Also Hard for Read-r Times Branching Programs Comment on: TR01-049 |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2001/049#comment1
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.
Thu, 25 Jul 2002 17:28:53 +0300https://eccc.weizmann.ac.il/report/2001/049#comment1
Paper TR01-049
| On Multi-Partition Communication Complexity of Triangle-Freeness |
Stasys Jukna,
Georg Schnitger
https://eccc.weizmann.ac.il/report/2001/049We 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.
Wed, 11 Jul 2001 18:08:04 +0300https://eccc.weizmann.ac.il/report/2001/049