This is a solid theory contribution. The reviewers mention the specialized nature of the problem setting. But given the strength of the results and the presentation clarity lauded by all reviewers, I think the paper should be awarded a spotlight presentation.