An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
Constraint satisfaction problems with advice
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
Noisy predictions only marginally better than random guessing suffice to provably reduce the search space in exact exponential algorithms for subset selection problems, with runtime speedup scaling smoothly with prediction quality under pairwise independence or no accuracy knowledge.
citing papers explorer
-
Warm-Starting All-Pairs Shortest Paths with Predictions
An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
-
Learning Augmented Exact Exponential Algorithms
Noisy predictions only marginally better than random guessing suffice to provably reduce the search space in exact exponential algorithms for subset selection problems, with runtime speedup scaling smoothly with prediction quality under pairwise independence or no accuracy knowledge.