BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Algorithmic Paradigms for Dynamic Graph Problems
DTSTART:20200423T140000
DTEND:20200423T150000
DTSTAMP:20260406T184248Z
UID:1ea293677f279d4c5ac549a39fdc98f6a416c85fec1e3edf4ca63ab4
CATEGORIES:Conferences - Seminars
DESCRIPTION:The talk will take place via zoom. Please click on the followi
 ng link: https://epfl.zoom.us/j/380717737\n\nBy: Thatchaphol Saranurak - T
 oyota Technological Institute at Chicago\nIC Faculty candidate\n\nAbstact\
 nIn the traditional view of computation\, a computational task is solved f
 rom scratch\, and then remains solved forever. It is increasingly clear th
 at this static model does not adequately capture the requirements of real-
 world computation. For instance\, in a communication network\, new links a
 ppear and disappear all the time. Recomputing everything from scratch (to 
 obtain\, for instance\, connectivity-information about the network) is cle
 arly wasteful. Similar dynamic scenarios arise in most modern applications
 \, including load balancing in parallel computation\, tracking communities
  in social networks\, financial fraud detection\, and routing.\nDynamic gr
 aph algorithms aim to address this issue\; they maintain information about
  graphs that undergo edge/vertex updates without recomputing everything fr
 om scratch after each update. \nThese algorithms are promising for all th
 e practical applications mentioned above and have deep theoretical applica
 tions. Unfortunately\, even the most basic graph problems\, such as graph 
 connectivity and shortest paths\, are still not well-understood in the dyn
 amic setting. \n   \nIn this talk\, I will talk about two general techn
 iques recently used to break decades-old barriers on many dynamic graph pr
 oblems: 1) dynamic expander decomposition and 2) local clustering.\nThe ne
 w development of these techniques on dynamic graphs\, in turn\, leads to e
 xciting applications even in the classical static setting. For example\, t
 hey improve the 50-year-old quadratic time bound for checking k-vertex-con
 nectivity to nearly linear time.\n\nBio\nThatchaphol Saranurak is a theore
 tical computer scientist\, currently holding a research assistant professo
 r position at Toyota Technological Institute at Chicago\, USA. \nHe compl
 eted his Ph.D. at KTH Royal Institute of Technology in 2018 where he was s
 upervised by Danupon Nanongkai.\nHis main research interest is on graph al
 gorithms with a current focus on dynamic\, local\, and distributed algori
 thms.\n\nMore information\n\n 
LOCATION:
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR