The field of learning-augmented algorithms has shown that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. However, the focus has been primarily on polynomial-time algorithms, where predictions enhance competitive ratios, approximation guarantees, or running times.
This paper raises the question of whether predictions can advance the frontier of exact exponential-time algorithms for NP-hard problems, answering affirmatively by proposing a general approach that augments a family of state-of-the-art exact algorithms for various subset selection problems.
We demonstrate that a noisy predictor that is only marginally better than random guessing is sufficient to provably reduce the search space, and the resulting runtime speedup scales smoothly with prediction quality. Importantly, our algorithms require only pairwise independence of predictions or do not require knowledge of the predictor's accuracy—both are strictly weaker and more realistic settings than typically assumed.
Blogger's Review: This paper illustrates the potential of learning-augmented algorithms in NP-hard problems, particularly in the context of exact exponential-time algorithms. By requiring only weak conditions for predictions, the authors provide a new perspective on solving complex problems, significantly enriching both the theoretical foundation and practical possibilities of algorithm design.