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:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6a5020c63fbb9
DTSTART;TZID=America/Toronto:20260710T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260710T123000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read
 inggroup-nathan-benedetto-proenca-why-are-sdp
SUMMARY:CombOpt ReadingGroup - Nathan Benedetto Proenca-Why are SDP Roundi
 ng\nAlgorithms Randomized?
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\n Nathan Benedetto Proenca\n\nAFFILIATION:\n Univers
 ity of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: Randomization is a po
 werful technique within theoretical\ncomputer science. There is strong th
 eoretical picture studying\ndistinct complexity models with access to ran
 dom bits\, in particular\nfocused on what types of algorithms can be de-r
 andomized. This\ndiscussion will not venture into this part of the litera
 ture\, rather\nquestioning an implicit assumption present when discussing
  the need\nfor random bits. Why is randomness helpful at all\, in partic
 ular in\nthe design of rounding algorithms in the SDP literature? Grante
 d\,\nthe value of randomness in other contexts is quite explicit. For\ne
 xample\, a quicksort implementation uses randomization to avoid worst\nca
 se inputs. The probabilistic method allows for simple constructions\nof c
 omplex objects by harvesting complexity from a randomness source.\nBut wh
 at purpose does randomness serve when rounding a SDP solution\ninto a sol
 ution to a NP-hard problem? Why Goemans and Williamson had\nto use a rand
 om hyperplane to turn vectors in the hypersphere into a\nedge-cut in a gr
 aph? This talk attempts to answer this question by\npresenting a couple 
 of theorems which connect the existence of\nrandomized rounding algorithm
 s to cornerstone results in functional\nanalysis.
DTSTAMP:20260709T222926Z
END:VEVENT
END:VCALENDAR