Finding Equal Subset Sums in the Pigeonhole Regime by Prof Pranjal Dutta

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.

In 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). 

Based on joint work with Deepak Bhati, Antoine Joux, Mahesh Sreekumar Rajasree, and Karol Węgrzycki, which got accepted in FOCS 2026. 

Biography: 

Pranjal Dutta is a Nanyang Assistant Professor in the College of Computing and Data Science (CCDS) at NTU Singapore. He is also an NTU Honours College (NHC) Faculty Fellow. 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 algebraic flavoured algorithmic questions.

RSVP for this talk:  https://forms.gle/2isMmWQB4Pw22k2g8