BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1207
DTSTAMP:20230914T125954Z
SUMMARY:Fast multivariate multipoint evaluation over finite fields
DESCRIPTION:Speaker: Mrinal Kumar (Indian Institute of Technology Bombay)\n
 \nAbstract: \nMultipoint evaluation is the computational task of evaluatin
 g a polynomial given as a list of coefficients at a given set of inputs. A
  straightforward algorithm for this problem is to just iteratively evaluat
 e the polynomial at each of the inputs. The question of obtaining faster-t
 han-naive (and ideally\, close to linear time) algorithms for this problem
  is a natural and fundamental question in computational algebra. In additi
 on to its own inherent interest\, faster algorithms for multipoint evaluat
 ion are closely related to fast algorithms for other natural algebraic que
 stions like polynomial factorization and modular composition.\nNearly line
 ar time algorithms have been known for the univariate multipoint evaluatio
 n for close to five decades due to a work of Borodin and Moenck but fast a
 lgorithms for the multivariate (or\, even bivariate) version have been muc
 h harder to come by. In a significant improvement to the state of art for 
 this problem in 2008\,  Umans and Kedlaya-Umans gave nearly linear time a
 lgorithms for this problem over field of small characteristic and over all
  finite fields respectively\, provided that the number of variables is at 
 most d^{o(1)} where d is the degree of the input polynomial in every varia
 ble.\nIn this talk\, we will discuss two new algorithms for this problem: 
 the first is a simple and natural algebraic algorithm over not-too-large f
 ields of small characteristic and the second is a (non-algebraic) algorith
 m for this problem over all finite fields. Both these algorithms run in ne
 arly linear time even when the number of variables is large. We will also 
 discuss an application to an upper bound for data structures for polynomia
 l evaluation and to an upper bound on the rigidity of Vandermonde matrices
 .\nThe talk is based on joint works with Vishwas Bhargava\, Sumanta Ghosh\
 , Zeyu Guo\, Chandra Kanta Mohapatra and Chris Umans.\n
URL:https://www.tcs.tifr.res.in/web/events/1207
DTSTART;TZID=Asia/Kolkata:20220530T110000
DTEND;TZID=Asia/Kolkata:20220530T120000
LOCATION:A-201 and Zoom
END:VEVENT
END:VCALENDAR