Tata Institute of Fundamental Research
The Natural Proofs Barrier Against Data Structure Lower Bounds
STCS Seminar
Speaker:
Tulasi Mohan Molli (BITS Pilani Hyderabad)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 17 Mar 2026, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A long-standing challenge in Theoretical Computer Science is to prove strong lower bounds for data structures in the cell probe model. Consider a data structure problem with data from a set D, queries from a set Q, and in the dynamic case, updates from a set U. The current state of the art in lower bounds is a query time of t = approximately on the order of log of |Q| (up to polylogarithmic factors) for static problems, and max(tq, tu) = approximately on the order of (log² n) for dynamic problems, where tq and tu are the query and update times and n = max(|Q|, |U|, log |D|). In this talk, we address this barrier by porting the celebrated Natural Proofs framework of Razborov and Rudich from circuit complexity to the data structure setting.This talk is based on joint work with Michal Koucký, Bruno Loff, and Michael Saks (STOC 2026) where we comprehensively survey the literature on data structure lower bounds in the cell probe model and show that almost all major proof techniques are natural within our framework. This includes static approaches like cell sampling and methods based on communication complexity, as well as dynamic techniques ranging from the classic chronogram method to the recent super-logarithmic lower bounds of Larsen and Yu [LY23]. We will also explore how these techniques connect to Coding Theory.Finally, we will see our conjectured family of pseudorandom data structure problems designed to fool the distinguishers inherent in these proofs. If our conjecture holds, then all natural lower bound techniques (which encompass all known methods except one) are fundamentally unable to improve upon the current state of the art.
Short Bio: Tulasi Mohan Molli is an Assistant Professor in the Department of Computer Science & Information Systems at BITS Pilani, Hyderabad Campus. He was previously a Postdoctoral Researcher at the University of Lisbon. He earned his PhD from the Tata Institute of Fundamental Research (TIFR), Mumbai, and holds both a BSc (Honors) and an MSc from the Chennai Mathematical Institute (CMI). He primarily works in Complexity Theory, specifically exploring data structure lower bounds and the fundamental barriers to proving lower bounds in general.
| Speaker: | Tulasi Mohan Molli (BITS Pilani Hyderabad) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 17 Mar 2026, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
A long-standing challenge in Theoretical Computer Science is to prove strong lower bounds for data structures in the cell probe model. Consider a data structure problem with data from a set D, queries from a set Q, and in the dynamic case, updates from a set U. The current state of the art in lower bounds is a query time of t = approximately on the order of log of |Q| (up to polylogarithmic factors) for static problems, and max(tq, tu) = approximately on the order of (log² n) for dynamic problems, where tq and tu are the query and update times and n = max(|Q|, |U|, log |D|). In this talk, we address this barrier by porting the celebrated Natural Proofs framework of Razborov and Rudich from circuit complexity to the data structure setting.This talk is based on joint work with Michal Koucký, Bruno Loff, and Michael Saks (STOC 2026) where we comprehensively survey the literature on data structure lower bounds in the cell probe model and show that almost all major proof techniques are natural within our framework. This includes static approaches like cell sampling and methods based on communication complexity, as well as dynamic techniques ranging from the classic chronogram method to the recent super-logarithmic lower bounds of Larsen and Yu [LY23]. We will also explore how these techniques connect to Coding Theory.Finally, we will see our conjectured family of pseudorandom data structure problems designed to fool the distinguishers inherent in these proofs. If our conjecture holds, then all natural lower bound techniques (which encompass all known methods except one) are fundamentally unable to improve upon the current state of the art.
Short Bio: Tulasi Mohan Molli is an Assistant Professor in the Department of Computer Science & Information Systems at BITS Pilani, Hyderabad Campus. He was previously a Postdoctoral Researcher at the University of Lisbon. He earned his PhD from the Tata Institute of Fundamental Research (TIFR), Mumbai, and holds both a BSc (Honors) and an MSc from the Chennai Mathematical Institute (CMI). He primarily works in Complexity Theory, specifically exploring data structure lower bounds and the fundamental barriers to proving lower bounds in general.