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:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69fa17de20238
DTSTART;TZID=America/Toronto:20240125T163000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240125T173000
URL:https://uwaterloo.ca/pure-mathematics/events/analysis-seminar-175
SUMMARY:Analysis Seminar
CLASS:PUBLIC
DESCRIPTION:ERIC CULF\, DEPARTMENT OF APPLIED MATHEMATICS\, UNIVERSITY OF W
 ATERLOO\n\n\"APPROXIMATION ALGORITHMS FOR NONCOMMUTATIVE CONSTRAINT SATISF
 ACTION\nPROBLEMS\"\n\nConstraint satisfaction problems (CSPs) are an impor
 tant topic of\ninvestigation in computer science. For example\, the proble
 m of finding\noptimal k-colourings of graphs\, Max-Cut(k)\, is NP-hard\, b
 ut it is easy\nto approximate in the sense that it is possible to find a c
 olouring\nthat satisfies a large fraction of the constraints of an optimal
  one.\nWe study a noncommutative variant of CSPs that is central in quantu
 m\ninformation\, where the variables are replaced by operators. In this\nc
 ontext\, even approximating general CSPs is known to be much harder\nthan 
 the classical case\, in fact uncomputably hard. Nevertheless\,\nMax-Cut(2)
  becomes efficiently solvable. We introduce a framework for\ndesigning app
 roximation algorithms for noncommutative CSPs\, which\nallows us to find c
 lasses of CSPs that are efficiently approximable\nbut not efficiently solv
 able. To determine the quality of our\napproximation algorithm\, we make u
 se of results from free probability\nto characterise a distribution arisin
 g from random matrices. This talk\nis based on work with Hamoon Mousavi an
 d Taro Spirig\n(arxiv.org/abs/2312.16765).\n\nThis seminar will be held bo
 th online and in person:\n\n* Room: MC 5479\n * Zoom link:\nhttps://uwater
 loo.zoom.us/j/94186354814?pwd=NGpLM3B4eWNZckd1aTROcmRreW96QT09
DTSTAMP:20260505T161630Z
END:VEVENT
END:VCALENDAR