BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1695
DTSTAMP:20260306T092350Z
SUMMARY:The Natural Proofs Barrier Against Data Structure Lower Bounds
DESCRIPTION:Speaker: Tulasi Mohan Molli (BITS Pilani Hyderabad)\n\nAbstract
 : \nA 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\, a
 nd in the dynamic case\, updates from a set U. The current state of the ar
 t 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\, wher
 e 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 Natura
 l Proofs framework of Razborov and Rudich from circuit complexity to the d
 ata structure setting.This talk is based on joint work with Michal Koucký
 \, Bruno Loff\, and Michael Saks (STOC 2026) where we comprehensively surv
 ey the literature on data structure lower bounds in the cell probe model a
 nd show that almost all major proof techniques are natural within our fram
 ework. This includes static approaches like cell sampling and methods base
 d on communication complexity\, as well as dynamic techniques ranging from
  the classic chronogram method to the recent super-logarithmic lower bound
 s of Larsen and Yu [LY23]. We will also explore how these techniques conne
 ct to Coding Theory.Finally\, we will see our conjectured family of pseudo
 random data structure problems designed to fool the distinguishers inheren
 t in these proofs. If our conjecture holds\, then all natural lower bound 
 techniques (which encompass all known methods except one) are fundamentall
 y unable to improve upon the current state of the art.\nShort Bio: Tulasi
  Mohan Molli is an Assistant Professor in the Department of Computer Scien
 ce & Information Systems at BITS Pilani\, Hyderabad Campus. He was previou
 sly a Postdoctoral Researcher at the University of Lisbon. He earned his P
 hD from the Tata Institute of Fundamental Research (TIFR)\, Mumbai\, and h
 olds both a BSc (Honors) and an MSc from the Chennai Mathematical Institut
 e (CMI). He primarily works in Complexity Theory\, specifically exploring
   data structure lower bounds and the fundamental barriers to proving low
 er bounds in general.\n
URL:https://www.tcs.tifr.res.in/web/events/1695
DTSTART;TZID=Asia/Kolkata:20260317T160000
DTEND;TZID=Asia/Kolkata:20260317T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR