REVIEW 2 major objections 6 minor 1 cited by
Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
T0 review · 2 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Pairwise predictions crack NP-hard permutation problems in polynomial time
desk verdict Sound and useful framework for exact poly-time algorithms for NP-hard permutation problems with pairwise predictions; just fix the abstract to state the independence assumption. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key machinery is a reduction through the noisy sorting without resampling (NSWR) problem, which turns pairwise predictions into an s-optimal permutation that is within O(log n) positions of the true optimum. The paper then shows that any problem which is decomposable or c-local becomes polynomial-time solvable when it is 'k-position enhanced' with k = O(log n), via two different dynamic programs: one for decomposable problems that enumerates candidate interval sets, and one for c-local problems that tracks a sliding window of c elements.
What would settle it
Take an instance of a decomposable problem (e.g., maximum acyclic subgraph) with two optimal solutions that are far apart, and define a prediction oracle whose errors are positively correlated: for a fixed block of elements, every comparison involving that block is wrong with probability 1, while other comparisons are correct. If the resulting s-optimal permutation deviates from the true optimum by more than O(log n) positions, then the reduction in Lemma 7 fails and the polynomial-time exact algorithm would return a suboptimal solution; this can be checked by running the algorithm and comparing its output to the known optimum.
Extended reading notes
Core claim
The central discovery is Theorem 1: if a permutation optimization problem P satisfies the decomposition property or is c-local, then P can be solved exactly with high probability in polynomial time using O(n log n) prediction queries, where each query is correct with probability at least 1/2 + ε. The proof combines the noisy-sorting-without-resampling result of Braverman and Mossel with dynamic programming: predictions first produce a permutation close to the hidden optimum, and then the decomposition or locality structure allows a polynomial-time DP to refine that approximation into an exact solution.
Load-bearing premise
The predictions are assumed to be independent of each other given the hidden optimal permutation, and each is correct with probability at least 1/2 + ε; if errors are correlated, the recovered ordering may not stay within O(log n) of the true optimum, and the polynomial-time guarantee collapses.
Editorial extensions
If this is right
- All five listed NP-hard problems—maximum acyclic subgraph, minimum linear arrangement, 1|prec|ΣC_j, TSP, and keyword auctions with externalities—admit exact polynomial-time algorithms when pairwise predictions with accuracy 1/2 + ε are available.
- The algorithm uses only O(n log n) prediction queries, making it parsimonious compared to querying all pairs.
- The framework extends automatically to any permutation optimization problem with the decomposition property or c-locality, which are broad structural conditions.
- The O(log n) position-enhancement bound is tight: if the enhancement is worsened to f(n) log n for any unbounded f, there exist decomposable and c-local problems that remain hard under the Exponential Time Hypothesis.
- A problem (Permutation Clique) remains hard even with O(log n) positional enhancement, showing that the decomposition/locality conditions are essential, not a general consequence of positional information.
Reading between the lines
- The independence assumption in the prediction model is strong: a real-world predictor whose errors are correlated (e.g., systematic bias about certain items) could make the s-optimal permutation drift far from the true optimum, breaking the O(log n) guarantee and hence the polynomial-time conclusion.
- The reduction might be extended to produce approximate solutions when predictions are weaker than 1/2 + ε, or when only a limited number of queries are affordable, by trading solution quality for query count.
- The decomposition and c-locality conditions could serve as a design template: problem designers may check whether a new permutation problem satisfies either condition to decide whether pairwise advice is a viable route to tractability.
- A natural testable extension is to replace the independence assumption with a weaker notion of 'almost independence' or to allow the algorithm to adaptively choose which pairs to query, potentially reducing the number of queries further.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a learning-augmented framework for NP-hard permutation problems. In the formal model (Definition 2), the algorithm can query, for every pair of elements, the relative order of the two elements in a fixed optimal permutation; each query is correct with probability at least 1/2+ε and the queries are independent conditioned on that hidden optimal permutation. The main theorem states that if a permutation problem's objective is either decomposable or c-local, then the problem can be solved exactly with high probability in polynomial time using O(n log n) prediction queries. The proof combines the Braverman–Mossel noisy-sorting result with new dynamic programs for k-position-enhanced versions of the problems. The framework is applied to Maximum Acyclic Subgraph, Minimum Linear Arrangement, the scheduling problem 1|prec|ΣC_j, TSP, and sponsored-search auctions with externalities. A final section gives ETH-based lower bounds showing that the O(log n) position-enhancement window is tight for some decomposable and c-local problems.
Significance. If the result stands, it is a substantial extension of learning-augmented algorithms: slightly-better-than-random pairwise advice makes a whole family of NP-hard permutation problems exactly solvable in polynomial time, with a parsimonious number of queries. The two structural properties, decomposability and c-locality, are clean and the DP constructions are natural. The paper has notable strengths: the Braverman–Mossel theorem is used as a black box, no fitted constants or reverse-engineered parameters appear, the O(n log n) query count is a genuine parsimony feature, and the lower-bound section tests the tightness of the O(log n) window. The main weakness is that the headline condition in the abstract and the informal theorem statement omits the independence assumption on which the result actually depends; without independence the advertised claim is false. This is a scope/communication issue rather than an error in the formal body, but it affects the paper's central claim as presented.
major comments (2)
- [Abstract; Section 1, Theorem 1; Section 2.1, Definition 2] The abstract and the statement of Theorem 1 advertise the prediction condition as "predictions are true with probability at least 1/2+epsilon". This condition is strictly weaker than the model actually used in the proof. Definition 2 additionally requires that all pairwise queries are independent conditioned on sigma*. That independence is load-bearing: it is needed for the Braverman-Mossel closeness theorem (Theorem 6) and hence for Lemma 7. Without independence, the advertised statement is false: with probability 1/2+epsilon return the true relative order for every pair, and with probability 1/2-epsilon return the exact reverse for every pair. Each individual query then has marginal accuracy 1/2+epsilon, but on the reversal event the unique s-optimal permutation is the reverse of sigma*, at displacement Theta(n), so no O(log n)-position enhancement and no polynomial-time exact recovery is obtained. Please state the independence condition in the abstract and in the informal theorem statement, or define the weaker model and discuss this obstruction explicitly.
- [Section 3.2; Section 4, Lemma 11] The c-local dynamic program is not fully specified for cyclic or boundary-dependent objectives such as TSP. The recurrence in Lemma 11 adds cost terms of the form cost_I(a_{sigma(i)},...,a_{sigma(i+c)}) as it places positions from left to right, but it never adds the closing edge d(v_{sigma(n)},v_{sigma(1)}) of a TSP tour. The claim in Section 3.2 that TSP is "trivially 1-local" because one can "easily reformulate to get rid of the last term" is not demonstrated, and the stated DP, as written, would compute a shortest Hamiltonian path rather than a shortest tour. A correct treatment requires a dummy start/end vertex, a fixed first vertex with the closing edge added at the end, or an explicit boundary convention in Definition 9. The same issue affects the first c slots in the keyword-auction example, whose costs depend on fewer than c predecessors. Please make the base case and boundary handling explicit in Lemma 11.
minor comments (6)
- [Section 4, Lemma 10 proof] In the text, "I′(i,i+s)" should read "I′(i,s)", and "we have it total n−1 subproblems" should read "we have in total n−1 subproblems".
- [Section 5.1, Proposition 13] In the edge rules, the diagonal vertices of G′ are written as "v_{\ell,\ell}"; these should be "v'_{\ell,\ell}" to avoid confusing vertices of G with vertices of G′.
- [Section 3.2] The phrase "j's influence on i's crt" should read "... on i's ctr" (click-through rate).
- [Section 5.1 and Section 5.2, Propositions 13–15] The quantities t′ and N should be typeset as 2^{t/c} and 2^{n/f(n)}. As rendered in the submitted text they appear as 2t/c and 2n/f(n), which would make the equalities t = c log t′ and n = f(n) log N false.
- [Section 4, Lemma 11] The recurrence should state explicitly that σ(i) is restricted to elements for which S(i)\{σ(i)} is a valid state in S(i−1). This restriction justifies the bound of at most 2k+1 choices and prevents transitions that would violate the position-enhancement constraints.
- [Section 2.1, Definition 9 footnote] The footnote giving the boundary convention for i≤c is abbreviated and hard to parse; please spell out how shorter windows are handled and how the cost function is defined for those cases.
Circularity Check
No significant circularity; the derivation is self-contained modulo the external Braverman-Mossel noisy-sorting theorem.
full rationale
The paper's derivation chain is not circular. Definition 2 fixes a probabilistic prediction model with independent pairwise queries conditioned on the hidden optimal permutation sigma*. The core reduction, Lemma 7, uses the external Braverman-Mossel results (Theorems 5 and 6) as a black box: from O(n log n) queries it obtains an s-optimal permutation pi* that is O(log n)-close to the hidden optimum, and then solves the k-position-enhanced version of the problem. The two DP lemmas, Lemmas 10 and 11, construct solutions from the k-position-enhanced assumption using only the decomposition/c-locality structure of the objective; no fitted parameter or target quantity is re-inserted into the hypothesis. The self-citations (e.g., [2] on parsimonious dense instances and [11] on externalities) are contextual or modeling references and are not load-bearing for Theorem 1. The only notable issue is a presentation/scope gap: the abstract and informal statement say predictions are correct with probability at least 1/2+epsilon, while Definition 2 additionally requires conditional independence of the queries; without independence the Braverman-Mossel closeness theorem can fail. That is a correctness/communication caveat, not circularity. The formal theorem is supported by an independent external result, so the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Braverman-Mossel Theorems 5 and 6: an s-optimal permutation for NSWR is within O(log n) of the hidden permutation, and can be found in n^{O(epsilon^{-4})} time with O(n log n) queries.
- domain assumption Prediction model of Definition 2: queries are independent conditioned on a fixed hidden optimal permutation, and each is correct with probability at least 1/2+epsilon.
- domain assumption Exponential Time Hypothesis (ETH) for hardness results.
Cite this review
Pith. "Pith review of Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems." pith.science (2026). https://pith.science/paper/QW3Y772T
@misc{pith2026250200841,
author = {Pith},
title = {Pith review of: Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/QW3Y772T}},
note = {Machine review of arXiv:2502.00841}
}
abstract
We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair $u,v$ of elements, whether $u$ is before $v$ or not in an optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of optimization problems including scheduling, network design and other graph permutation problems, these predictions allow to solve them in polynomial time with high probability, provided that predictions are true with probability at least $1/2+\epsilon$. Moreover, this can be achieved with a parsimonious access to the predictions.
Forward citations
Cited by 1 Pith paper
-
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
A verification layer around learned pruning of NP-hard problems yields prediction-independent worst-case guarantees and PAC-learnable parameters.
Reference graph
Works this paper leans on
-
[1]
Approximation algorithms for combinatorial optimization with predictions, 2024
Antonios Antoniadis, Marek Eliáš, Adam Polak, and Moritz Venzin. Approximation algorithms for combinatorial optimization with predictions, 2024. https://arxiv.org/abs/2411.16600 arXiv:2411.16600
arXiv 2024
-
[2]
Parsimonious learning-augmented approximations for dense instances of NP -hard problems
Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Parsimonious learning-augmented approximations for dense instances of NP -hard problems. In Proc. 41st Int. Conf. Machine Learning (ICML) , volume 235, pages 2700--2714, 2024
work page 2024
-
[3]
Noisy sorting without resampling
Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proc. 19th Symp. Discret. Algorithms (SODA) , page 268–276, 2008
work page 2008
-
[4]
Sorting from noisy information, 2009
Mark Braverman and Elchanan Mossel. Sorting from noisy information, 2009. https://arxiv.org/abs/0910.1191 arXiv:0910.1191
arXiv 2009
-
[5]
Learning-Augmented Maximum Independent Set
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-Augmented Maximum Independent Set . In Approx., Random., and Comb. Optim. Algorithms and Techniques (APPROX/RANDOM) , volume 317, pages 24:1--24:18, 2024
work page 2024
-
[6]
Max-Cut with $\epsilon$-Accurate Predictions
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Max-cut with -accurate predictions, 2024. https://arxiv.org/abs/2402.18263 arXiv:2402.18263
work page Pith review arXiv 2024
-
[7]
Faster matchings via learned duals
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Proc. 35th Adv. Neural Inf. Processing Syst. (NeurIPS) , 2021
work page 2021
-
[8]
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-augmented streaming algorithms for approximating max-cut, 2025. https://arxiv.org/abs/2412.09773 arXiv:2412.09773
work page Pith review arXiv 2025
Show all 25 references
-
[9]
Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords
Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords . American Economic Review , 97(1):242–259, March 2007
2007
-
[10]
Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning-augmented k-means clustering. In Proc. 10th Int. Conf. Learning Representations (ICLR) , 2022
2022
-
[11]
Externalities among advertisers in sponsored search
Dimitris Fotakis, Piotr Krysta, and Orestis Telelis. Externalities among advertisers in sponsored search. In Proc. 4th Int. Symp. on Algorithmic Game Theory ( SAGT ) , volume 6982, pages 105--116, 2011
2011
-
[12]
Approximate cluster recovery from noisy labels
Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Approximate cluster recovery from noisy labels. In Proc. 35th Conf. on Learning Theory (COLT) , 2022
2022
-
[13]
Towards better models of externalities in sponsored search auctions
Nicola Gatti, Marco Rocco, Paolo Serafino, and Carmine Ventre. Towards better models of externalities in sponsored search auctions. Theoretical Computer Science , 745:150--162, 2018
2018
-
[14]
Constraint satisfaction problems with advice, 2024
Suprovat Ghoshal, Konstantin Makarychev, and Yury Makarychev. Constraint satisfaction problems with advice, 2024. https://arxiv.org/abs/2403.02212 arXiv:2403.02212
2024 arXiv
-
[15]
Parsimonious learning-augmented caching
Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious learning-augmented caching. In Proc. 39th Int. Conf. Machine Learning (ICML) , volume 162, pages 9588--9601, 2022
2022
-
[16]
Which problems have strongly exponential complexity? J
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. , 63(4):512--530, 2001
2001
-
[17]
R. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations , pages 85--103. Plenum Press, 1972
1972
-
[18]
E.L. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. , 2:75--90, 1978
1978
-
[19]
Alexander Lindermayr and Nicole Megow. ALPS . https://algorithms-with-predictions.github.io/
-
[20]
Slightly superexponential parameterized problems
Daniel Lokshtanov, D \' a niel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput. , 47(3):675--702, 2018
2018
-
[21]
Competitive caching with machine learned advice
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM , 68(4), 2021
2021
-
[22]
Allocating online advertisement space with unreliable estimates
Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Proc. 8th ACM Conf. on Electronic Commerce (EC) , page 288–294, New York, NY, USA, 2007
2007
-
[23]
Improved learning-augmented algorithms for k-means and k-medians clustering
Thy Dinh Nguyen, Anamay Chaturvedi, and Huy Nguyen. Improved learning-augmented algorithms for k-means and k-medians clustering. In Proc. 11th Int. Conf. Learning Representations (ICLR) , 2023
2023
-
[24]
Discrete-convex-analysis-based framework for warm-starting algorithms with predictions
Shinsaku Sakaue and Taihei Oki. Discrete-convex-analysis-based framework for warm-starting algorithms with predictions. In Proc. 36th Adv. Neural Inf. Processing Syst. (NeurIPS) , 2022
2022
-
[25]
Hal R. Varian. Position auctions. International Journal of Industrial Organization , 25(6):1163--1178, 2007
2007
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.