BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1358
DTSTAMP:20231205T044029Z
SUMMARY:Fast Numerical Multivariate Multipoint Evaluation
DESCRIPTION:Speaker: Prahladh  Harsha (TIFR)\n\nAbstract: \nMultipoint eval
 uation is the computational task of evaluating a polynomial given as a lis
 t of coefficients at a given set of evaluation inputs. A straightforward a
 lgorithm for this problem is to just iteratively evaluate the polynomial a
 t each of the inputs. The question of obtaining faster-than-naive (and ide
 ally\, close to linear time) algorithms for this problem is a natural and 
 basic question in computational algebra.\n \nThe classical FFT algorithm 
 gives such an algorithm for the special case of univariate polynomials and
  a well-structured set of evaluation points (say roots of unity). Only as 
 recently as last year\, was the multivariate version of this problem for a
 ll sets of evaluation points resolved for finite fields due to the works o
 f Bhargava\, Ghosh\, Guo\, Kumar & Umans.\n \nThe case of infinite fields
  (eg\, reals\, rationals) is complicated due to subtleties arising from th
 e bit-complexity of the output compelling one to work with either an appro
 ximate version of the problem or an exact version where the algorithm is a
 llowed to run in time nearly-linear in the output size. Only as recently a
 s 2021\, was the univariate version of this problem over infinite fields r
 esolved by Moroz.\n \nIn this talk\, we will show how to extend these res
 ults to obtain similar nearly-linear time results for the multivariate ver
 sion of the problem over infinite fields such as rationals\, reals both in
  the approximate and exact setting.\n \n[Joint work with Sumanta Ghosh\, 
 Simao Herdade\, Mrinal Kumar and Ramprasad Saptharishi]\n
URL:https://www.tcs.tifr.res.in/web/events/1358
DTSTART;TZID=Asia/Kolkata:20231205T160000
DTEND;TZID=Asia/Kolkata:20231205T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR