BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Information Theory Seminar
SUMMARY:Graph Joinings\, Graph Isomorphism\, and Reversibl
 e Markov Chains - Prof Andrew Nobel\, UNC Chapel H
 ill
DTSTART;TZID=Europe/London:20260304T140000
DTEND;TZID=Europe/London:20260304T150000
UID:TALK244771AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/244771
DESCRIPTION:Every weighted\, undirected graph describes a simp
 le random walk on its vertex set\, which is a reve
 rsible Markov chain.  In this talk I will describe
  recent work on graph joinings that leverages this
  elementary connection\, in conjunction with ideas
  from optimal transport\, to gain insights into bo
 th graph isomorphism and couplings of reversible M
 arkov chains.  Informally\, a joining of two graph
 s is a product graph from which the given graphs c
 an be recovered via marginalization.  Given two gr
 aphs with labeled vertices\, the optimal graph joi
 ning (OGJ) problem identifies a joining that minim
 izes the weighted degree of vertex pairs with diff
 erent labels. For suitable families of labeled gra
 phs\, including trees and forests\, OGJ can detect
  and identify isomorphisms between any two graphs 
 in the family.  In a different direction\,  I will
  describe several results showing how graph joinin
 gs yield new insights into the rigidity of reversi
 ble couplings of reversible Markov chains.\n\nJoin
 t work with Yang Xiang\, Phuong Hoang\, Bongsoo Yi
 \, and Kevin McGoff.
LOCATION:MR5\, CMS Pavilion A
CONTACT:Dr Varun Jog
END:VEVENT
END:VCALENDAR