BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d1ff19397a4
DTSTART;TZID=America/Toronto:20250228T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250228T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-xiao-hu
SUMMARY:Tutte colloquium-Xiao Hu
CLASS:PUBLIC
DESCRIPTION:TITLE:What is New in Join-Aggregate Query Processing?\n\nSPEAKE
 R:\n Xiao Hu\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 55
 01\n\nABSTRACT: Join-aggregate queries defined over commutative semirings\
 nsubsume a wide variety of common algorithmic problems\, such as graph\npa
 ttern matching\, graph colorability\, matrix multiplication\, and\nconstra
 int satisfaction problems. Developing efficient algorithms for\ncomputing 
 join-aggregate queries in the conventional RAM model has\nbeen a holy grai
 l in database theory. One of the most celebrated\nresults in this area is 
 the Yannakakis algorithm dating back to 1981.\nDespite its prominence as a
  textbook solution\, no improvements in its\ncomplexity have been made ove
 r the past 40 years. In this talk\, I will\npresent the first algorithm th
 at improves upon Yannakakis for\ncomputing acyclic join-aggregate queries.
  Moreover\, this algorithm is\nproven to be output-optimal among all combi
 natorial algorithms. One\napplication is an output-optimal algorithm for c
 hain matrix\nmultiplication over sparse matrices. Beyond combinatorial alg
 orithms\,\nI will also show how fast matrix multiplication can further spe
 ed up\nthe processing of conjunctive queries\, a critical subclass of\njoi
 n-aggregate queries. Finally\, I will highlight a few interesting\nopen pr
 oblems in this area.\n\n \n\n 
DTSTAMP:20260405T062009Z
END:VEVENT
END:VCALENDAR