We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i>₀ for some absolute constant <i>k</i>₀, and either: ... more >>>

The Group Isomorphism problem consists in deciding whether two input
groups $G_1$ and $G_2$ given by their multiplication tables are
isomorphic. We first give a 2-round Arthur-Merlin protocol for the
Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$
of size $n$, Arthur uses ... more >>>

It is known \cite{BHZ87} that if every language in coNP has a
constant-round interactive proof system, then the polynomial hierarchy
collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that
#SAT, the #P-complete function that outputs the number of satisfying
assignments of a Boolean ... more >>>