Stasys Jukna, Georg Schnitger

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