CFCS Invited Talks

An FPRAS for two terminal reliability in directed acyclic graphs

  • Dr. Heng Guo, University of Edinburgh
  • Time: 2023-12-08 16:00
  • Host: Dr. Tianren Liu
  • Venue: Room 204, Courtyard No.5, Jingyuan


I will describe a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs. I will give some background on the problem and discuss some related results / problems as well.
Joint work with Weiming Feng.



Heng Guo is a reader in algorithms and complexity in the School of Informatics, the University of Edinburgh. Before Edinburgh, he has worked in London and Berkeley. He completed his Ph.D. thesis in the University of Wisconsin - Madison in 2015, which has won the EATCS Distinguished Dissertation award. He has also won the best paper award of ICALP 2018 (joint with Mark Jerrum).