NSETH and Consequences

Title of the Talk: NSETH and Consequences
Speaker: Prof. Venkatesh Raman (IIT Palakkad; IMSc Chennai (Retd.))
Date: Wednesday, 11 February 2026
Time: 3:45 PM – 4:45 PM
Venue: CSE-LH

Abstract

The Strong Exponential Time Hypothesis (SETH) is a well-known conjecture that has driven fine-grained complexity research to establish (conditional) tight lower bounds for several NP-hard as well as polynomial-time solvable problems. NSETH is a relatively recent, nondeterministic variation of SETH. In this talk, we will examine NSETH and discuss its consequences for demonstrating the non-existence of fine-grained reductions for certain problems.

Bio

Prof. Venkatesh Raman obtained his Ph.D. from the University of Waterloo, Canada, and served as a faculty member at the Institute of Mathematical Sciences (IMSc), Chennai, from 1991 to 2024. He is currently associated with IIT Palakkad. He has also served the ACM India Council in various roles, including as President from 2022 to 2024. His primary research interests are in data structures and algorithms, particularly succinct data structures, parameterized algorithms, and exact algorithms.