ITU researcher wins one of the most prestigious awards in the field of theoretical computer science
The Best Paper Award at the annual IEEE Symposium on Foundations of Computer Science (FOCS) is co-authored by associate professor at IT University of Copenhagen, Nutan Limaye. It is the first time the award goes to a researcher at a Danish university.
Computer Science DepartmentResearchawardsalgorithms
Written October 19, 2021 2:52 PM by Jari Kickbusch
Together with Srikanth Srinivasan (Aarhus University) and Sébastien Tavenas (LAMA, Université Savoie Mont Blanc), associate professor at IT University of Copenhagen, Nutan Limaye, wrote the research article, Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits, which was awarded the Best Paper Award at the annual IEEE Symposium on Foundations of Computer Science (FOCS).
The paper’s results are a step towards understanding the answer to one of the classic million-dollar questions in the field of Computational Complexity, namely the P vs. NP question. Though known for decades this mathematical problem remains unsolved. The question is at the heart of understanding the limits of computers’ problem-solving powers and the nature of computation. Computational complexity directly impacts the trust in cryptographic systems, which relies on evidence for the impossibility of being broken, and guides all research in algorithms, including day-to-day artefacts such as navigation apps in your smartphone.
- The question of P vs. NP was formalised during the cold-war in 1970s and is primarily ascribed to Steve Cook who was in the US and Leonid Levin was in USSR then. It has gained importance because it connects many practical problems to each other. In our work, we study the algebraic variant of the problem. We provide insights into how hard it is to compute certain polynomials. We show that there are classes of polynomials which cannot be computed efficiently using certain algorithms, says Nutan Limaye.
The three authors started writing the paper in 2019, when they were working with related computational challenges. At the time, Nutan Limaye was working at Indian Institute of Technology Bombay and in fact she only started in her position as associate professor at IT University of Copenhagen in September 2021.
First time for Danish Universities
The Best Paper Award from FOCS has made quite an impression on her new colleagues at IT University. Head of Computer Science Department, Professor Peter Sesoft, notes that it is the first time the award goes to researchers at a Danish university:
- This is exceptional and very prestigious. FOCS is one of the two world-leading conferences in algorithms. Just publishing a paper there is a sign of elite achievement; much more so receiving a Best Paper Award, he says.
The result gained immediate attention among elite researchers in theoretical computer science. The day after the manuscript was published online, Rahul Santhanam at Oxford University tweeted ”complexity paper of the year so far” and Thatchapol Saranurak at Michigan University called it “a big breakthrough.“ Nutan Limaye’s colleague, Professor Thore Husfeldt, is not surprised by the attention:
- Progress in Computational Complexity is incredibly hard and slow, despite attracting some of the best minds in the field, he says and continues: - so when a good result finally comes around, it resonates with the entire field. This is an impressive achievement by Nutan and her co-authors. For once it makes sense to use superlatives like world class and groundbreaking.