Skip to main content ITU
Logo
  • Programmes
    • BSc Programmes
    • BSc in Global Business Informatics
    • BSc in Digital Design and Interactive Technologies
    • BSc in Software Development
    • BSc in Data Science
    • Applying for a BSc Programme
    • MSc Programmes
    • MSc in Digital Innovation & Management
    • MSc in Digital Design and Interactive Technologies
    • MSc in Software Design
    • MSc in Computer Science
    • MSc in Data Science
    • MSc in Games
    • Applying for an MSc Programme
    • Student Life
    • Women in tech
    • Student Organisations at ITU
    • Labs for students
    • Practical Information for International Students
    • Study Start
    • Study and Career Guidance
    • Guest Students
    • Who can be a Guest Student
    • ITU Summer University
    • Exchange Student
    • Become an exchange student at ITU
    • Open House
    • Open House - MSc Programmes
    • Open House - BSc programmes
  • Professional Education
    • Master in IT
    • Master in IT Management
    • Single Subjects
    • About single subjects
    • Contact
    • Contact us here
  • Research
    • Departments
    • Business IT Department
    • Computer Science Department
    • Digital Design Department
    • Research Groups and Labs
    • Research Groups
    • Labs
    • Research Centres
    • Centre for Computer Games Research
    • Center for Computing Education Research
    • Centre for Digital Welfare
    • Centre for Information Security and Trust
    • European Blockchain Centre
    • Research Centre for Government IT
    • Research Institutes
    • Danish Institute for IT Program Management
    • Selected Research Themes
    • Artificial intelligence
    • Big Data
    • Climate IT
    • Computer games
    • Blockchain
    • Digitalization
    • IT security
    • Find a Researcher
    • Faculty Search
    • PhD Programme
    • About the PhD Programme
    • Available PhD Positions
    • PhD Courses
    • Research Ethics and Integrity
    • Good Scientific Practice
    • PhD Defences
    • Technical Reports
    • Technical Reports
  • Collaboration
    • Collaboration with students
    • Project collaboration
    • Project Market
    • Student worker
    • Project postings
    • Job and Project bank
    • Portraits of ITU graduates
    • Employer Branding
    • IT Match Making
    • Hiring an ITU student or graduate
    • Make a post in the job bank
    • Research collaboration
    • Licensing Opportunities
    • Open Entrepreneurship
    • Research collaboration
    • Industrial PhD
    • Hire an Industrial PhD
    • Innovation and entrepreneurship
    • ITU Business Development
    • ITU Startup programme
    • Startup stories
  • About ITU
    • Vacancies
    • Press
    • ITU Alumni
    • News
    • Calendar
    • Contact
    • About ITU
  • DK
ITU researcher wins one of the most prestigious awards in the field of theoretical computer science
ITU  /  Press  /  News from ITU  /  ITU researcher wins one of the most prestigious awards in the field of theoretical computer science

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.

News

Rasmus Ejlers Møgelberg and Jonas Fritsch receive grants from IRFD

Rasmus Ejlers Møgelberg and Jonas Fritsch receive grants from IRFD

May 10, 2022

The two researchers – from Computer Science and Digital Design at the IT University respectively – have each secured a grant of approximately 2.8 million kroner for their research projects.

European Blockchain Center announces new partnership

European Blockchain Center announces new partnership

April 28, 2022

The European Blockchain Center at the IT University of Copenhagen is partnering with SupraOracles to explore future collaborative efforts to provide value to the blockchain industry on a global scale.

Can robots help prevent anxiety attacks in children?

Can robots help prevent anxiety attacks in children?

April 26, 2022

Morten Roed Frederiksen from Computer Science at ITU has received 1.6 million kroner from Independent Research Fund Denmark for at research project that aims to make robots better at understanding human emotion. The goal is to create technology that may help children with anxiety.

Professor Sebastian Risi receives grant to develop policy learning with neural networks

Professor Sebastian Risi receives grant to develop policy learning with neural networks

April 20, 2022

Professor in the Digital Design Department at the IT University of Copenhagen, Sebastian Risi, has received a grant of approximately 550,000 Danish kroner for his work on neural cellular automata to grow neural network policies capable of adapting to novel complex reinforcement learning tasks.

New research may help improve Copenhagen’s bicycle infrastructure

New research may help improve Copenhagen’s bicycle infrastructure

March 28, 2022

A newly released research paper shows how network analysis can serve as a cost-efficient support tool for bicycle infrastructure planning. The research has been conducted by analyzing the street network in Copenhagen based on data from OpenStreetMap.

ITU professor takes critical approach to green tech, secures prestigious grant

ITU professor takes critical approach to green tech, secures prestigious grant

March 17, 2022

Professor at the IT University of Copenhagen’s Business IT department Steffen Dalsgaard has won the prestigious ERC Consolidator Grant. The almost two million Euro grant will enable him and his colleagues to critically examine IT and sustainability across the globe.

We need to talk about marine renewable energy

We need to talk about marine renewable energy

March 3, 2022

Denmark lacks neither ocean waves nor pioneering scientists and innovators who are dreaming about harnessing energy from them. Professor at IT University of Copenhagen Brit Ross Winthereik, who headed research into initiatives in wave energy innovation around the Atlantic, explains why we are still waiting to see a booming wave energy industry.

IT University to suspend all cooperation with Russia and Belarus

IT University to suspend all cooperation with Russia and Belarus

March 2, 2022

Along with Denmark’s other universities, ITU will be suspending all bilateral institutional cooperation with the states of Russia and Belarus going forward. Current exchange programme participants will not be affected by the measure.

New blockchain governance standard to generate trust and accountability in the market

New blockchain governance standard to generate trust and accountability in the market

February 28, 2022

The new standard, developed by Professor Roman Beck at the IT-University and Danish Standard, will ensure greater transparency, interoperability, and accountability in the use of blockchain and DLT systems. Professor Roman Beck has recently received AIS’s Impact Award for his work in the field.

Using Minecraft to explore climate change topics with school children

Using Minecraft to explore climate change topics with school children

February 8, 2022

Few of the world’s most popular games deal directly with climate issues. However, games can still be used to make gamers think about real world problems, says Associate Professor, Hans-Joachim Backe, who is developing tools for teachers to discuss climate issues based on for example Minecraft.

Digitizing the Amazon: How to use the rainforest without ruining it

Digitizing the Amazon: How to use the rainforest without ruining it

February 8, 2022

There is a lot of hope that the digital, material, and biological innovations of the Fourth Industrial Revolution will help us save the Amazon rainforest. However, the real impact of the new bio economy is yet to be revealed. Researchers from the IT University will study the outcome of Amazônia 4.0.

How do we secure critical technologies from tampering? The answer may be sending them into orbit

How do we secure critical technologies from tampering? The answer may be sending them into orbit

January 20, 2022

At the IT University of Copenhagen, Associate Professor Bernardo David, is working on a joint research project that aims to send satellites that power cryptographic and blockchain applications into orbit in order to secure them from tampering and to enable time-based primitives based on communication delays.

ITU PhD fellow named Game Changer by gaming industry mainstay

ITU PhD fellow named Game Changer by gaming industry mainstay

January 5, 2022

PhD fellow at the Center for Computer Games Research at the IT University of Copenhagen, Leon Y. Xiao, is new to ITU, but his research into the legal and ethical aspects of the gaming industry has already made an impact. Gaming industry mainstay, GamesIndustry.biz, recently named him one of 2021’s Game Changers.

Martin Tvede Zachariasen steps down as Vice-Chancellor

Martin Tvede Zachariasen steps down as Vice-Chancellor

December 20, 2021

Martin Tvede Zachariasen steps down as Vice-Chancellor of the IT University after three years in office. Martin Tvede Zachariasen’s resignation takes effect December 31, 2021.

European Blockchain Center announces International blockchain school and Nordic Blockchain Summit in early 2022

European Blockchain Center announces International blockchain school and Nordic Blockchain Summit in early 2022

December 8, 2021

The International Blockchain School will be held at IT University of Copenhagen on January 24-28th, 2022. On the final day of classes, the students will present their projects at the public event, Nordic Blockchain Summit.

ITU’s Mogens Jacobsen wins prestigious art grant

ITU’s Mogens Jacobsen wins prestigious art grant

December 8, 2021

The artist Mogens Jacobsen who teaches at Digital Design at the IT University of Copenhagen creates art inspired by technology and scientific research. Today, he is the recipient of a grant from the prestigious Niels Wessel Bagge Art Foundation.

ITU researcher secures prestigious fellowship to empower citizen cooperation

ITU researcher secures prestigious fellowship to empower citizen cooperation

December 7, 2021

Associate Professor of Computer Science at the IT University of Copenhagen, Luca Maria Aiello, has won the Carlsberg Foundation’s prestigious Young Researcher Fellowship for a project that aims to facilitate citizen coordination in the face of global challenges such as climate change.

CDV Podcast: Could your cat be used to store your family photos?

CDV Podcast: Could your cat be used to store your family photos?

December 1, 2021

The incomprehensible amounts of digital data we store is a real climate burden. In the Center for Digital Welfare's podcast, host Anders Kjærulff and Assistant Professor James Maguire, discuss research initiatives on environmentally friendly data storage.

Business travel plays vital role in economic growth, according to ITU researcher

Business travel plays vital role in economic growth, according to ITU researcher

November 24, 2021

As a thought experiment Associate Professor of Computer Science at the IT-University, Michele Coscia, theorized that global GDP would drop significantly if business travel on a global scale ceased – now the global COVID-19 shutdown has proven his theory in practice.

Public debate: Do Big Data and law enforcement go hand in hand?

Public debate: Do Big Data and law enforcement go hand in hand?

November 10, 2021

On December 14, the IT University headed research project CUPP and PROSA are hosting a public seminar and debate on data driven policing. Panelists include Palantir Technologies representative Paula Kift, former DPO of the National Police of Denmark, Christian Wiese Svanberg, and Jesper Lund from the IT Political Association.

Contact us

Phone
+45 7218 5000
E-mail
itu@itu.dk

All contact information

Web Accessibility Statement

Find us

IT University of Copenhagen
Rued Langgaards Vej 7
DK-2300 Copenhagen S
Denmark
How to get here

Follow us

ITU Student /
Privacy /
EAN-nr. 5798000417878/
CVR-nr. 29 05 77 53

This page is printed from https://en.itu.dk/research/portalplaceholder?layoutfraction=top&langRef=https://pure.itu.dk/portal/da/organisations/digital-design(d065e6c2-4fae-4d68-ad04-70aec25d2d5e)/clippings.html?page=29