{"ID":6497731,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09289","arxiv_id":"2607.09289","title":"Faster Exact Algorithms for Equal-Subset-Sum","abstract":"We study exact algorithms for Equal-Subset-Sum in the worst-case setting: given a set $S$ of $n$ integers, find two distinct subsets $A,B\\subseteq S$ whose sums are equal. We establish a new state-of-the-art bound for this problem by improving the fastest known algorithm, due to Randolph and Węgrzycki (STOC 2026), from $O^*(1.7067^n)$ time and space to an algorithm that runs in $O^*(1.6994^n)$ time and uses $O^*(1.5664^n)$ space. We also improve the best known polynomial-space running time, due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), from $O^*(2.6817^n)$ to $O^*(2.5430^n)$. Finally, we investigate time-space tradeoffs for this problem and improve the running times achievable under a broad range of exponential-space bounds.","short_abstract":"We study exact algorithms for Equal-Subset-Sum in the worst-case setting: given a set $S$ of $n$ integers, find two distinct subsets $A,B\\subseteq S$ whose sums are equal. We establish a new state-of-the-art bound for this problem by improving the fastest known algorithm, due to Randolph and Węgrzycki (STOC 2026), from...","url_abs":"https://arxiv.org/abs/2607.09289","url_pdf":"https://arxiv.org/pdf/2607.09289v1","authors":"[\"Ryosuke Yamano\",\"Tetsuo Shibuya\"]","published":"2026-07-10T11:03:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}