Speaker:

金策 (UC Berkeley)

Time:

• 11:00-12:00 Beijing Time
• January 5, 2026 (Monday)

Venue:

四号科研楼A区 518

Abstract:

We study the Pigeonhole Equal Subset Sum problem, which is a total-search variant of the Subset Sum problem introduced by Papadimitriou (1994): we are given a set of n positive integers {w_1,…,w_n} with the additional restriction that ∑_{i=1}^n w_i < 2^n - 1, and want to find two different subsets A,B ⊆ [n] such that ∑_{i∈A} w_i = ∑_{i∈B} w_i. Previously, the best known runtime for Pigeonhole Equal Subset Sum was O^*(2^{n/2}), via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelhöfer, and Santha, ESA 2022). Our main result is a faster randomized algorithm in O^*(2^{n/3}) time. Unlike many previous works in this area, our approach does not use the representation method, but rather exploits a simple structural characterization of input instances with few solutions. Based on two papers which appeared in ICALP 2024 and ESA 2025, jointly with Hongxun Wu, Ryan Williams, and Stan Zhang.

Speaker Bio:

Ce Jin is a Miller Postdoctoral Fellow at UC Berkeley. He completed his PhD at MIT in 2025. Before that, he was an undergraduate student in Yao Class, Tsinghua University. He has a broad interest in theoretical computer science.