The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there is a positive integer combination of numbers a1,...,an that is equal to b. The problem can be solved in pseudopolynomial time, while there are specialized cases, such as when b exceeds the Frobenius number of a1,...,an, for which a solution is guaranteed to exist.
In this talk, I will consider the search version of this problem, where the goal is to find the solution. explores the concept of totality in USS. The challenge in this setting is to actually find a solution, even though we know its existence is guaranteed. We focus on the instances of USS where solutions are guaranteed for large b. I will show that if b is slightly larger than the Frobenius number, then a solution can be found in polynomial time.
We then show how our results extend to Integer Programming with Equalities (ILPE), highlighting conditions under which ILPE becomes total. We investigate the diagonal Frobenius number, which is the appropriate generalization of the Frobenius number to this context. In this setting, we give a polynomial-time algorithm to find a solution of ILPE. The bound obtained from our algorithmic procedure for finding a solution almost matches the recent existential bound of Bach, Eisenbrand, Rothvoss, and Weismantel (2024).
This talk is based on joint work with Antoine Joux, Miklos Santha, and Karol Wegrzycki.
Short Bio:
Divesh Aggarwal is an Associate Professor in the Department of Computer Science and a Principal Investigator at the Centre for Quantum Technologies at the National University of Singapore. He earned his PhD from ETH Zurich, where he focused on the theoretical foundations of cryptography. His research spans lattice-based cryptography, pseudorandomness, computational complexity, and coding theory. He has made significant contributions to the field, including developing some of the fastest known algorithms for lattice problems and advancing the understanding of their computational hardness. His work also includes pioneering constructions in non-malleable codes and extractors, which play a crucial role in modern cryptographic protocols. In recognition of his innovative research, he was awarded the NRF Investigatorship in 2024, a prestigious honor granted to leading scientists in Singapore to support high-impact, risk-taking research
