08/04/2025
Continuing our journey through fascinating mathematical ideas, we’re excited to bring you the next session in our Beyond Lectures series! 🎉 This time, we shift gears from classical physics to theoretical computer science, as we dive into a clever twist on the well-known 3SUM problem and its implications in the world of fine-grained complexity.
📝 Topic: Revisiting the 3SUM Problem in Preprocessed Universes
🎙 Speaker: Pratyush Sharma
📖 Abstract:
We revisit the 3SUM problem in the preprocessed universes setting. We present an algorithm that, given three sets A,B,C of n integers, preprocesses them in quadratic time so that, for any subsets 𝐴',𝐵',𝐶', it can decide whether there exist a∈A', b∈B' ,c∈C' such that a+b=c, in time O(n^1.5 logn).
Beyond the algorithm itself, we’ll also explore what this result means in the broader context of computational complexity and how it contributes to our understanding of preprocessing and query efficiency in algorithm design.
🎤 About the Speaker:
Pratyush is a third-year undergraduate in the Mathematics Department. He pursued a research internship at Bocconi University, Italy, in the field of Theoretical Computer Science. Pratyush has a wide range of interests and loves participating in (and struggling through) all sorts of competitions that pique his curiosity. A passionate enthusiast of Maths Olympiads, you’ll often find him fixated on a single problem for hours. Outside the academic grind, he enjoys Chess and Table Tennis, and statistically speaking, has the highest probability of being found in his hostel at any given moment.
🗓 Date: 09/04/2025
📍 Venue: LH316
⏰ Time: 6 – 7 PM
Join us for an exciting session that explores cutting-edge ideas in algorithm design and computational complexity! Whether you’re into theoretical CS, algorithmic puzzles, or just love a good challenge, this talk has something for you.
Even if you’re new to the topic, feel free to swing by—Pratyush is always happy to chat about olympiads, competitions, and navigating research as an undergrad. P
