Nutan Limaye: Computational complexity

CAST IT (video)

Nutan Limaye is an associate professor at IT University of Copenhagen and an internationally leading researcher in computational complexity.

Nutan’s research focus is on the most prestigious and fundamental questions in computer science, namely: which problems can be solved with limited computational resources? Her recent breakthrough result, with Srinivasan and Tavenas, received the best paper award at the Foundations of Computer Science conference in 2021 and shows that algebraic circuits of constant size require superpolynomial depth.

We ask Nutan what these words even mean, and take a deep dive into the foundations of computer science. What are computational problems, computational models, algorithms, and how does one reason scientifically about such broad concepts? In particular, how does an impossibility result even make sense: how can one prove that a problem can never be solved, no matter how many clever ideas we (or anybody else) may have in the future?

For more information: [e-mail]