Professor Nutan Limaye receives DKK 12.8 million for research on algebraic complexity
Professor Nutan Limaye at the IT University of Copenhagen has been awarded DKK 12.8 million from the Carlsberg Foundation for her project Algebraic Hardness and Applications (AHA). The project addresses central questions in computational complexity theory: which computational problems admit efficient algorithms, and what structural barriers prevent efficient solutions?
AHA will develop new connections between algebraic methods and complexity theory, with a particular focus on the power of randomness and parallelism in computation. While randomness is widely used in algorithms and cryptographic protocols, it remains a major open challenge to understand when randomised computation can be derandomised, and what resources are fundamentally required to do so.
A key theme of the project is the relationship between sequential and parallel complexity: whether problems in P necessarily admit highly efficient parallel algorithms, and how algebraic hardness assumptions can inform these questions.
Nutan Limaye is a core member of the Basic Algorithms Research Copenhagen (BARC) centre and serves on its steering committee. The project will strengthen Danish research in theoretical computer science through international collaborations and contributions to leading complexity and algorithms venues.