BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Finding patterns\, short cycles and long shortest p
 aths in graphs
DTSTART:20220207T150000
DTEND:20220207T160000
DTSTAMP:20260406T194641Z
UID:91a5aafc12f64dd0041589286e2b27d53d6f08f6ec618558a6a64ea6
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Mina Dalirrooyfard - MIT\nIC Faculty candidate\n\nAbstrac
 t\nThis talk is about finding useful structures in a graph using fast algo
 rithms\, and/or showing that no such fast algorithms exist under popular h
 ypotheses from the field of Fine-Grained Complexity. These graph structure
 s can be a small fixed sized pattern subgraph\, or more specific bigger st
 ructures such as the longest shortest path in the graph whose length is kn
 own as the diameter of a graph. Finding these structures has many applicat
 ions\, from protein-protein interactions in biology to anomaly detection i
 n networks.\n\nWe first focus on the Graph Pattern Detection or Subgraph I
 somorphism Problem that asks for detecting a fixed-sized subgraph pattern 
 in a given graph. We give the first fine-grained lower bounds for this pro
 blem for arbitrary patterns. We also consider the "counting" version of th
 is problem and show that it is hard "on average" when the input graph is d
 rawn from the uniform distribution. Then we move on to patterns that are n
 ot necessarily fixed sized and are represented by graph parameters such as
  diameter\, radius\, eccentricity and girth. In this part we show that the
  folklore 2-approximation algorithm for computing the diameter of the grap
 h is tight under SETH\, a fine-grained complexity hypothesis. We will conc
 lude with ideas for future work.\n\nBio\nMina Dalirrooyfard is a final yea
 r PhD student at MIT\, advised by Virginia Vassilevska Williams. Her resea
 rch area is  graph algorithms and fine-grained complexity\, with a partic
 ular focus on graph pattern detection\, graph parameter estimation and fin
 e-grained average-case complexity.\n\nMore information
LOCATION:https://epfl.zoom.us/j/66274431324?pwd=bmxIL0lrVTdJdjY0UzdycUtISF
 kzUT09
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR