Computer Science Seminar
Date: Monday, 09 October 2023
Time: 03:45 PM
Venue: Lecture Hall 202, CMI
Fine-grained Complexity (of Lattice Problems)
Divesh Aggarwal
National University of Singapore.
09-10-23

---

Abstract

Traditionally, the computational hardness of a problem X is established by finding an efficient reduction from a known NP-hard problem Y. These results imply that there is no efficient algorithm for X unless there is an efficient algorithm for Y. More recently, with the hope of obtaining more precise hardness results, we started looking at a more fine-grained variant of these hardness results. These hardness results are of particular importance for computational problems relevant in cryptography.

I will begin with an introduction to the standard fine-grained complexity assumptions. Then I will talk about implications to the hardness of lattice problems, and also discuss the difficulty of showing hardness results for some of these computational problems. Lattice problems are computational problems that modern cryptosystems are based on, particularly if one wants the cryptosystems to be resistant to quantum attacks.

The talk will only assume background in fundamental algorithms and discrete mathematics, and no background in complexity theory.

Speaker Bio:
Divesh Aggarwal is an Associate Professor in the Department of Computer Science and a Principal Investigator in the Centre for Quantum Technologies, at National University of Singapore. Prior to joining NUS, he was a postdoctoral researcher in EPFL, and in NYU. He received his PhD from the Department of Computer Science at ETH Zurich. His primary research interests are in the foundations of lattice-based cryptography, and in pseudorandomness. He is also more broadly interested in computational complexity and coding theory. He has state-of-the-art results for fastest algorithms of lattice problems, fine-grained hardness of lattice problems, and also state-of-the-art constructions of non-malleable codes and extractors, which are important tools in cryptography.