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:69d158ca7b0d6
DTSTART;TZID=America/Toronto:20241206T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241206T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-robert-andrews
SUMMARY:Tutte colloquium-Robert Andrews
CLASS:PUBLIC
DESCRIPTION:TITLE: Constant-Depth Arithmetic Circuits for Linear Algebra Pr
 oblems\n\nSPEAKER:\n Robert Andrews\n\nAFFILIATION:\n University of Waterl
 oo\n\nLOCATION:\n MC 5501\n\nABSTRACT: What is the computational complexit
 y of the greatest common\ndivisor (GCD) of two univariate polynomials? The
  Euclidean algorithm\nprovides a polynomial-time solution\, and fast varia
 nts of the\nEuclidean algorithm can compute the GCD in nearly-linear time.
  The GCD\ncan also be expressed in a linear-algebraic form. Basic tasks in
 \nlinear algebra\, such as computing determinants and solving linear\nsyst
 ems\, can be performed in O(log^2 n) parallel time\, and this can be\nused
  to compute the GCD in O(log^2 n) parallel time. This algorithm\ndoes not 
 take advantage of any structure present in the resulting\nlinear systems\,
  so in principle one could compute the GCD in parallel\neven faster.\n\nIn
  this talk\, I will describe a new algorithm that computes the GCD in\nO(l
 og n) parallel time by using a combination of polynomial\ninterpolation an
 d Newton's identities for symmetric polynomials. In\nfact\, this algorithm
  can be implemented as an arithmetic circuit of\nconstant depth. Similar i
 deas yield constant-depth circuits to compute\nthe resultant\, Bézout coe
 fficients\, and squarefree decomposition.\n\n \n\n 
DTSTAMP:20260404T183034Z
END:VEVENT
END:VCALENDAR