A Faster Algorithm for Pigeonhole Equal Sums

An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search problem proposed by Papadimitriou (1994): given n positive integers w₁, , wₙ of total sum ₈=₁ⁿ wᵢ < 2ⁿ-1, the task is to find two distinct subsets A, B n such that ₈ ₀wᵢ=₈ ₁wᵢ. Similar to the status of the Subset Sum problem, the best known algorithm for Pigeonhole Equal Sums runs in O^* (2^n/2) time, via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelh\"ofer, and Santha, 2022). Our main result is an improved algorithm for Pigeonhole Equal Sums in O^* (2^0. 4n) time. We also give a polynomial-space algorithm in O^* (2^0. 75n) 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.