^July August – 2011

Let a,b,c,… in S_n be random permutations on n elements, chosen at uniform distribution. What is the distribution of the permutation obtained by a fixed word in the letters a,b,c,…, such as ab,a^2, a^2bc^2b, or aba^(-2)b^(-1)? More concretely, do these new random permutations have uniform distribution? In general, a free word w in F_k is called uniform if for every finite group G, the word map $w: G^k to G$ induces uniform distribution on G (given uniform distribution on G^k). So which words are uniform? This question is strongly connected to the notion of primitive words in the free group $F_k$. The word w is called primitive is it belongs to some basis, i.e. a generating set of size $k$. It is an easy observation that a primitive word is uniform. It was conjectured that the converse is also true. We prove it for F_2. In a very recent joint work with O. Parzanchevski, we manage to prove the conjecture in full. Akey ingredient of the proofs is a new algorithm to detect primitive elements.

A maximal independent set (MIS) on a graph is an inclusion-maximal set of mutually non-adjacent nodes. This basic symmetry breaking structure is vital for many distributed algorithms. There is a simple and elegant randomized algorithm that computes an MIS in O(log n) rounds. However, despite much effort, there has been no improvement in the general case for decades, leaving a large gap to the known lower bound of Omega(sqrt(log n)) rounds. We present a randomized algorithm that achieves a running time of O(sqrt(log n log log n)) on forests. In contrast to previous techniques achieving sublogarithmic running times, our approach does not rely on any bound on the number of independent neighbors (possibly with regard to an orientation of the edges). We therefore hope that it might ultimately contribute to improved algorithms for the general case.