Corelab Seminar

Eleni Bakali
Markov chains and phase transitions for TotP-complete problems

We consider weighted versions of TotP-complete problems. We study the complexity of computing these weighted sums and show the existence of phase transition from NP-hard to approximate to approximable with FPRAS. We also study Markov chains for these problems and show the existence of phase transitions from exponential to polynomial mixing time.