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:20250309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cea344bbf41
DTSTART;TZID=America/Toronto:20251128T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20251128T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-euiwoong-lee-0
SUMMARY:Tutte Colloquium - Euiwoong Lee
CLASS:PUBLIC
DESCRIPTION:TITLE:Asymptotically Optimal Hardness for k-Set Packing and k-M
 atroid\nIntersection\n\nSPEAKER:\n Euiwoong Lee\n\nAFFILIATION:\n Universi
 ty of Michigan\n\nLOCATION:\n MC 5501\n\nABSTRACT: For any epsilon > 0\, 
 we prove that k-Dimensional Matching\nis hard to approximate within a fact
 or of k/(12 + epsilon) for large k\nunless NP \\subseteq BPP. Listed in Ka
 rp's 21 NP-complete problems\,\nk-Dimensional Matching is a benchmark comp
 utational complexity problem\nwhich we find as a special case of many cons
 trained optimization\nproblems over independence systems including: k-Set 
 Packing\, k-Matroid\nIntersection\, and Matroid k-Parity. For all the afor
 ementioned\nproblems\, the best known lower bound was an Omega(k /log(k))-
 hardness\nby Hazan\, Safra\, and Schwartz. In contrast\, state-of-the-art\
 nalgorithms achieved an approximation of O(k). Our result narrows down\nth
 is gap to a constant and thus provides a rationale for the observed\nalgor
 ithmic difficulties. \n\nThe crux of our result hinges on a novel approxi
 mation preserving\ngadget from R-degree bounded k-CSPs over alphabet size 
 R to\nkR-Dimensional Matching. Along the way\, we prove that R-degree boun
 ded\nk-CSPs over alphabet size R are hard to approximate within a factor\n
 Omega_k(R) using known randomised sparsification methods for CSPs. \nJoint
  work with Ola Svensson and Theophile Thiery
DTSTAMP:20260402T171132Z
END:VEVENT
END:VCALENDAR