2 papers
cs.LO2020
Solving Random Parity Games in Polynomial Time
Richard Combes, Mikael Touati
We consider the problem of solving random parity games. We prove that parity games exibit a phase transition threshold above , so that when the degree of the graph that define…
stat.ML2018
Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
Richard Combes, Mikael Touati
We consider the problem of estimating from sample paths the absolute spectral gap of a reversible, irreducible and aperiodic Markov chain over a fi…