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