Nutan Limaye receives a grant from DFF
Associate Professor Nutan Limaye receives DKK 1.7 million from the Independent Research Fund Denmark (DFF) for the project "Formula complexity of polynomials and lower bounds"
A step toward answering the VF vs. VP question
Associate Professor Nutan Limaye from ITU and member of BARC received DKK 1.7 million from the Independent Research Fund Denmark to work on the model of algebraic formulas. Mathematicians have studied polynomials for centuries, but the exploration of their computational complexity is rather recent.
It is known that any polynomial that has small algebraic formulas is efficiently computed by parallel algorithms. This correspondence raises a natural question, known as the VF vs. VP question. "Does any efficiently computable polynomial have efficient parallel algorithms?"
The goal of this project is to answer the following related questions: (1) Can one multiply many large matrices using efficient parallel non-commutative algorithms? (2) Can one show the limits of the lower bound proof strategies using a unified framework? Answering these questions will push the envelope. Recent works, also by the PI, show that it will need new ideas. And it will be a step toward answering the VF vs. VP question (and the Boolean P vs. NC question).
Nutan Limaye is associate professor at ITU and a member of the BARC steering committee.