We give a new method for analysing the mixing time of a Markov chain using
path coupling with stopping times. We apply this approach to two hypergraph
problems. We show that the Glauber dynamics for independent sets in a
hypergraph mixes rapidly as long as the maximum degree \Delta of ... more >>>

The d-to-1 conjecture of Khot asserts that it is hard to satisfy an \epsilon fraction of constraints of a satisfiable d-to-1 Label Cover instance, for arbitrarily small \epsilon > 0. We prove that the d-to-1 conjecture for any fixed d implies the hardness of coloring a 4-colorable graph with C ... more >>>