Magnus Bordewich, Martin Dyer, Marek Karpinski

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

Venkatesan Guruswami, Sai Sandeep

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