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:68276ea466444
DTSTART;TZID=America/Toronto:20241206T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241206T163000
URL:/combinatorics-and-optimization/events/tutte-colloq
 uium-robert-andrews
SUMMARY:Tutte colloquium-Robert Andrews
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: Constant-Depth Arithmetic Circuits for Linea
 r Algebra Problems\n\nSPEAKER:\n Robert Andrews\n\nAFFILIATION:\n Universi
 ty of À¶Ý®ÊÓƵ\n\nLOCATION:\n MC 5501\n\nABSTRACT: What is the computation
 al complexity of the greatest common\ndivisor (GCD) of two univariate poly
 nomials? The Euclidean algorithm\nprovides a polynomial-time solution\, an
 d fast variants of the\nEuclidean algorithm can compute the GCD in nearly-
 linear time. The GCD\ncan also be expressed in a linear-algebraic form. Ba
 sic tasks in\nlinear algebra\, such as computing determinants and solving 
 linear\nsystems\, 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 algorith
 m\ndoes not take advantage of any structure present in the resulting\nline
 ar systems\, so in principle one could compute the GCD in parallel\neven f
 aster.\n\nIn this talk\, I will describe a new algorithm that computes the
  GCD in\nO(log n) parallel time by using a combination of polynomial\ninte
 rpolation and Newton's identities for symmetric polynomials. In\nfact\, th
 is algorithm can be implemented as an arithmetic circuit of\nconstant dept
 h. Similar ideas yield constant-depth circuits to compute\nthe resultant\,
  Bézout coefficients\, and squarefree decomposition.\n\n \n\n \n 
DTSTAMP:20250516T165812Z
END:VEVENT
END:VCALENDAR