A new state-of-the-art bound is established for Equal-Subset-Sum in the worst-case setting and the running times achievable under a broad range of exponential-space bounds are improved.
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\k{e}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\k{e}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.
A new quantum algorithm solving worst-case $k-SUM in time $\widetilde O(n^{\Psi_k})$, which is not only faster for all $k$ congruent to $3$ or $6$ modulo $7, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances.
N. Chukhin, Alexander S. Kulikov, Maksim Levitskii et al.· 1 citation
The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates.
A Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/3})$ queries are given.
A polynomial time algorithm is obtained that achieves a $(k/2^k)-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, and is an extension of a recently established Gaussian comparison inequality used to resolve the Weak Simplex Conjecture in coding theory.
The upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle.
Gaia Carenini· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
