BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.17.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20211107T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20221106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20221026T123000
DTEND;TZID=America/New_York:20221026T133000
DTSTAMP:20240121T174027Z
CREATED:20230817T174027Z
LAST-MODIFIED:20240121T174027Z
UID:10001269-1666787400-1666791000@cmsa.fas.harvard.edu
SUMMARY:Clique listing algorithms
DESCRIPTION:Speaker: Virginia Vassilevska Williams (MIT) \nTitle: Clique listing algorithms \nAbstract: A k-clique in a graph G is a subgraph of G on k vertices in which every pair of vertices is linked by an edge. Cliques are a natural notion of social network cohesiveness with a long history. \nA fundamental question\, with many applications\, is “How fast can one list all k-cliques in a given graph?”. \nEven just detecting whether an n-vertex graph contains a k-Clique has long been known to be NP-complete when k can depend on n (and hence no efficient algorithm is likely to exist for it). If k is a small constant\, such as 3 or 4 (independent of n)\, even the brute-force algorithm runs in polynomial time\, O(n^k)\, and can list all k-cliques in the graph; though O(n^k) time is far from practical. As the number of k-cliques in an n-vertex graph can be Omega(n^k)\, the brute-force algorithm is in some sense optimal\, but only if there are Omega(n^k) k-cliques. In this talk we will show how to list k-cliques faster when the input graph has few k-cliques\, with running times depending on the number of vertices n\, the number of edges m\, the number of k-cliques T and more. We will focus on the case when k=3\, but we will note some extensions. \n(Based on joint work with Andreas Bjorklund\, Rasmus Pagh\, Uri Zwick\, Mina Dalirrooyfard\, Surya Mathialagan and Yinzhan Xu)
URL:https://cmsa.fas.harvard.edu/event/collquium_102722/
LOCATION:CMSA Room G10\, CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Colloquium
ATTACH;FMTTYPE=image/png:https://cmsa.fas.harvard.edu/media/CMSA-Colloquium-10.26.22.png
END:VEVENT
END:VCALENDAR