Aarhus University Seal

Special talk by Nutan Limaye on the limits of efficient computation: an algebraic complexity perspective

Info about event

Time

Friday 18 November 2022,  at 10:00 - 11:00

Location

Nyugaard-395

Title: The limits of efficient computation: an algebraic complexity perspective Abstract: Complexity theory attempts to understand the limits of efficient computation. Efficiency is measured in terms of resources such as time or space. And the notion of computation is formalized by specifying the rules of computation. The central question that drives the area is: how hard is it to compute certain important and computationally interesting functions? In this talk, we will approach this question from the algebraic complexity perspective. Specifically, we will study how hard it is to compute certain polynomials. Polynomials are mathematical objects that arise naturally in many areas of computer science such as coding theory, cryptography, and algorithm design. Valiant in 1979 formalized models of computation of polynomials and started their systematic study. He posed the following fundamental questions:

• Are there explicit polynomials that cannot be computed efficiently? This is the famous VP vs. VNP question.

• Are there explicit polynomials that are easy to compute by sequential algorithms that have no efficient parallel algorithms? This is the VP vs. VNC question.

Over the last decade, my research has provided partial answers to some of these fundamental questions. In this talk, I will present an overview of my research contributions. I will end with some compelling research directions that emerge from my work.