BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20260101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20260805T110000
DTEND;TZID=Asia/Kolkata:20260805T120000
DTSTAMP:20260922T093750
CREATED:20260813T064916Z
LAST-MODIFIED:20260813T064916Z
UID:2632-1785927600-1785931200@homecse.iitd.ac.in
SUMMARY:Finding Equal Subset Sums in the Pigeonhole Regime by Dr. Pranjal Dutta
DESCRIPTION:Abstract: The Pigeonhole Equal Subset Sum problem (PESS)\, introduced by Papadimitriou (1994)\, asks: given n positive integers bounded by M with total sum less than 2^n − 1\, find two distinct subsets with the same sum. A solution is guaranteed by the pigeonhole principle\, yet finding one efficiently has been a longstanding challenge.\nIn this talk\, I will introduce the problem and discuss its connections to Subset Sum\, Equal Subset Sum\, and total search problems. First\, I will describe a simple birthday-paradox-based algorithm for the weak-pigeonhole regime\, and explain how combining it with Karmarkar–Karp differencing yields faster algorithms for dense instances. Second\, I will discuss a deterministic poly(n) · M^{o(1)}-time algorithm when M = 2^{o(n)}\, based on block merging and modular pruning. I will also discuss a conditional lower bound from lattice problems\, as well as an average-case poly(n) · M^{1/4}-time algorithm. This beats the best known algorithm which runs in poly(n)·M^{1/3} time (Jin-Wu\, ICALP 2024\, Jin-Williams-Zhang\, ESA 2025).\nBased on joint work with Deepak Bhati\, Antoine Joux\, Mahesh Sreekumar Rajasree\, and Karol Węgrzycki\, which got accepted in FOCS 2026. \nBio: Pranjal currently holds the Nanyang Assistant Professorship in the College of Computing and Data Science (CCDS) at Nanyang Technological University (NTU) Singapore. He spent Fall 2025 at Simons Institute as a Simons-Berkeley Fellow as well as Jane Street Research Fellow. Before joining NTU\, he was a postdoc at NUS Singapore\, hosted by Prof. Divesh Aggarwal. He obtained his PhD from CMI\, advised by Prof. Nitin Saxena and he was supported by Google PhD Fellowship. His PhD work won the ACM India Doctoral Dissertation Award 2023. He is broadly interested in Theoretical Computer Science\, with focus on algberaic flavoured algorithmic questions.
URL:https://homecse.iitd.ac.in/event/finding-equal-subset-sums-in-the-pigeonhole-regime-by-dr-pranjal-dutta/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR