Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of evaluation inputs. A straightforward algorithm for this problem is to just iteratively evaluate the polynomial at each of the inputs. The question of obtaining faster-than-naive (and ideally, close to linear time) algorithms for this problem is a natural and basic question in computational algebra.
The 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 all sets of evaluation points resolved for finite fields due to the works of Bhargava, Ghosh, Guo, Kumar & Umans.
The case of infinite fields (eg, reals, rationals) is complicated due to subtleties arising from the bit-complexity of the output compelling one to work with either an approximate version of the problem or an exact version where the algorithm is allowed to run in time nearly-linear in the output size. Only as recently as 2021, was the univariate version of this problem over infinite fields resolved by Moroz.
In this talk, we will show how to extend these results to obtain similar nearly-linear time results for the multivariate version of the problem over infinite fields such as rationals, reals both in the approximate and exact setting.
[Joint work with Sumanta Ghosh, Simao Herdade, Mrinal Kumar and Ramprasad Saptharishi]
13th December 2023 marks P.W. Andersons 100th birth anniversary. Anderson (1923-2020) was one of the most successful theoretical physicists in his time. His insights, methods, model building, finding solutions and making predictions had far reaching implications in several branches in science. Based on my personal appreciation of Anderson's research from my PhD days, and later as a long time collaborator, I will describe what I believe to be a secret behind Anderson's remarkable success and present some examples. Briefly, Anderson, a theorist par excellence, was guided by nature, in the form of experimental results at each and every step.
[The talk will also be livecast on zoom]
Zoom link: https://zoom.us/j/95038155052
Passcode: 272075
Over many centuries, after the concept of raga emerged in Indian classical
music, there have been many attempts to classify them. The most successful
semi-quantitative classification is the Venkatamakhi Melakartha system in
17th century. This system first defines precisely the nature of parent ragas
and assigns all other ragas as derived from a parent uniquely. This also
inspired Bhatkande to organise the Hindustani ragas using the concept of
Thaats. We critically examine these ancient concepts and practices from a
computational music perspective. The techniques developed by the Music
Technology group at IIT Madras form the backbone of this analysis. The
methods developed for this analysis have wide ranging application in many
other areas and these will be briefly mentioned.
Reference: On the concept of Raga Parentage in Carnatic Music. Jom
Kuriokose, Veena Suresh, Shrey DUtta, Hema Murthy and M V N Murthy. To
appear in JNMR 2023.