Professor portrait: Nutan Limaye is pushing the boundaries of complexity theory
On 22 May 2025 at 14:30, Professor Nutan Limaye from the section Theoretical Computer Science will present her inaugural lecture in Auditorium 0 at the IT University of Copenhagen. The lecture is entitled “My reflections on the last two decades and Complexity Theory”.
Nutan LimayeAbout ITUEventsResearchProfessor portrait
Written 1 May, 2025 08:43 by Mette Strange Mortensen
Professor Nutan Limaye was in her own words “reasonably good at math”, when she was in school. She was drawn to algorithms and saw how they affected so many things in human nature. Humans have an innate tendency to design efficient solutions for everyday problems. For example, we often try to find the optimal route from point A to point B or try to find the best deal while shopping. The combination of being reasonably good at math and liking algorithmic thinking later made her find her way into the research field of complexity theory.
Computational complexity theory is one of the basic research areas in computer science. The foundations of this research area can be found in the early works of the British mathematician and logician Alan Turing, who invented the Turing Machine and was also famously involved in decrypting the German codes during World War II. Complexity theory shares close connections to many areas of mathematics such as combinatorics, probability theory, and algebra.
“My research is mainly theoretical. So, in the short-term, it may not seem to have any real-life impact. However, it has connections to several practical areas. For example, when we say data is secure, like when using a credit card, it's because the data is encrypted and sent through a secure channel. Encryption works by applying a function to the data, which is hard to invert. The existence of a function that is ‘hard to invert’ ensures that, the data cannot be decrypted by a malicious adversary. My work attempts to prove that certain functions are hard to compute, which is quite crucial for cryptography," says Professor Nutan Limaye.
On 22 May 2025 at 14:30, Nutan Limaye will present her inaugural lecture at IT University of Copenhagen. The lecture will be on her current research in complexity theory and is entitled: “My reflections on the last two decades and Complexity Theory”.
Groundbreaking research sparks new questions
While complexity theory has been around for a long time, there is still much more to discover within the field.
“My current work focuses on computing polynomials and trying to understand their complexity. We were able to establish that certain polynomials, which have efficient sequential algorithms cannot be computed by efficient parallel algorithms. This hardness result that we proved in 2021 has given rise to many new questions.” says Nutan Limaye about her recent result.
One of the biggest challenges in algebraic complexity theory is the P vs. NP problem, or VP vs. VNP question as it is known in the setting of computing polynomials. This is the main area of research of Nutan Limaye. Her recent result with her co-authors takes a small step towards resolving this big open problem. When asked about what lies ahead, she elaborates on what is on the horizon for her:
“My next big question is looking into proving whether tree structures are more complicated than DAG structures in the setting of computing polynomials. In a tree structure you take two objects, combine them together, then two other objects and combine them together, and then take the output of those and then combine them together, so it kind of looks like a tree. In a DAG structure, a computation can be reused multiple times, not just once. This could look like a property being owned by multiple people, making the structure look more complex. While the DAG structure looks more complicated than the tree structure, in the context of computing polynomials, we do not know how to prove that mathematically.”
Was not meant to become a researcher
Nutan Limaye has now been working as a researcher for 20 years.
“I ended up in this field by a bit of an accident. When I had finished my basic education, I felt a pressure to find a job and settle down, and I did not want to do that. The solution was to continue to study, and then there was the opportunity to do a PhD, so I did that instead,” says Professor Nutan Limaye.
In her first years as a researcher, she was not sure whether she fits in academia. To challenge the stereotypes about what a researcher looks like, she has started her own podcast, where she interviews other academic researchers on how they got to where they are and what keeps them going. Her podcast is called “Life of a researcher”.
“For the first few years of my research life, I always wondered, “do I belong here in academia?”. But now I have found a place for myself. Being a researcher gives me a lot of choice and freedom in my work life. I can choose to work on what excites me. I hope the research, I choose to do, can become useful to the world.
Theis Duelund Jensen, Press Officer, phone +45 2555 0447, email