{"id":"63010fe9-b75d-44e5-8889-9c3f367c8259","arxiv_id":"2502.00841","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"With pairwise predictions that are correct with probability just above 1/2, a class of NP-hard permutation problems (decomposable or c-local objectives) can be solved exactly in polynomial time using only O(n log n) queries.","lead":"This paper shows that if a machine learning model can predict, for any pair of items, which one should come first in an optimal solution, many NP-hard ordering problems become solvable exactly in polynomial time. The result gives a general recipe: use noisy pairwise predictions to get a near-correct ordering, then a dynamic program to finish the job, and it covers scheduling, graph layout, and routing problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The formal proof is sound under Definition 2, but the advertised condition \"predictions true with probability 1/2+eps\" omits the independence clause on which Lemma 7 really depends.","rationale":"I read the paper in good faith as claiming a conditional theorem: under the formal noisy-permutation model of Definition 2, decomposable and c-local permutation problems are exactly solvable in polynomial time with high probability using O(n log n) queries. The proof is a clean reduction to Braverman-Mossel: Theorem 5/6 provide an s-optimal permutation within O(log n) of the hidden sigma*, and Lemmas 10-11 show that O(log n)-position-enhanced decomposable or c-local problems are poly-time solvable. I checked the DP recurrences, the decomposition accounting for MinLA, the c-local state transition, and the hardness reductions; I did not find an internal inconsistency. The weakest point is exactly the independence of the prediction queries, which the Reader also identified. The concern is load-bearing because Lemma 7 uses the Braverman-Mossel closeness theorem, and that theorem needs the independence assumption. The correlated two-scenario construction shows that marginal accuracy 1/2+eps alone is not enough: with constant probability the maximum-agreement permutation is Theta(n) away from sigma*. This does not refute the formal theorem, because Definition 2 includes independence, but it does show that the abstract and informal theorem statement overstate the robustness of the result. Since the paper clearly states the model before the theorem, I do not think the verdict should change; the caveat should be surfaced more prominently in the abstract. Hence UNCHANGED.","tokens_in":13166,"tokens_out":23004,"duration_ms":248536,"concrete_test":"Simulate the two-scenario correlated model on n elements with eps fixed: with probability 1/2+eps output the true pairwise order of sigma* for all pairs, and with probability 1/2-eps output the exact reverse for all pairs. Compute an s-optimal permutation (in this model it is sigma* in the first case and reverse(sigma*) in the second) and measure max_i |sigma*(i) - pi*(i)|. Repeating shows the displacement is Theta(n) with constant probability 1/2-eps, demonstrating that Theorem 6 fails as soon as the independence clause in Definition 2 is dropped, and that the abstract's condition alone is insufficient.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reduction in Lemma 7 is valid when Definition 2 holds, and the DP lemmas are internally consistent. The load-bearing condition is not merely 1/2+eps marginal accuracy: it is the independence of all pairwise queries conditioned on the hidden optimal permutation sigma*. The abstract and the informal statement of Theorem 1 state only that predictions are true with probability at least 1/2+eps, which is strictly weaker. Without independence, Braverman-Mossel's closeness theorem (Theorem 6) can fail dramatically. Concretely, take a scenario Z: with probability 1/2+eps return the true pairwise order of sigma* for every pair, and with probability 1/2-eps return the exact reverse for every pair. Each individual query is then correct with marginal probability 1/2+eps, but whenever Z=reversed the unique s-optimal permutation is the reverse of sigma*, at displacement Theta(n). No O(log n)-position enhancement is available, so the polynomial-time exact recovery argument has no warm start. Thus the central claim as informally advertised is false for correlated error distributions; the formal theorem survives only because Definition 2 explicitly assumes independence. This is a scope/communication gap rather than an internal proof error.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13389,"tokens_out":31911,"duration_ms":311764,"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":[{"comment":"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":"Abstract; Section 1, Theorem 1; Section 2.1, Definition 2"},{"comment":"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.","section":"Section 3.2; Section 4, Lemma 11"}],"minor_comments":[{"comment":"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":"Section 4, Lemma 10 proof"},{"comment":"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":"Section 5.1, Proposition 13"},{"comment":"The phrase \"j's influence on i's crt\" should read \"... on i's ctr\" (click-through rate).","section":"Section 3.2"},{"comment":"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":"Section 5.1 and Section 5.2, Propositions 13–15"},{"comment":"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":"Section 4, Lemma 11"},{"comment":"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.","section":"Section 2.1, Definition 9 footnote"}],"recommendation":"major_revision","confidential_remarks":"I am recommending major revision because the independence assumption and the TSP boundary handling need to be fixed in the final version. The formal model in Section 2.1 is correct, and the missing pieces are local and fixable; I see no basis for rejection. There is no concern about novelty or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is worth engaging. The main result—using Braverman-Mossel noisy sorting as a warm start, then running a DP on a k-position-enhanced problem—is real and works. The decomposition property and c-locality are genuinely useful sufficient conditions, and the applications to Max Acyclic Subgraph, MinLA, scheduling, TSP, and keyword auctions are correctly verified. The ETH lower bounds (Propositions 13–15) show the O(log n) position-enhancement bound is tight, which is a nice addition.\n\nThe formal machinery is sound. Lemma 7 is a clean reduction: BM gives an s-optimal permutation pi* close to sigma*, and relabeling by pi*^{-1} gives a k-position-enhanced instance. Lemmas 10 and 11 are correct DPs; the set-guessing arguments are within the stated O(2^k) bounds. I checked the decomposition recurrences for MinLA and the scheduling problem—they add up correctly.\n\nWhere the paper is soft: the abstract and Theorem 1 claim predictions are true with probability at least 1/2+epsilon without the independence clause that Definition 2 actually includes. The stress-test scenario is a fair one: if all queries are either all correct or all reversed with probability 1/2+/-epsilon, each query is marginally correct with probability 1/2+epsilon, but the s-optimal permutation is the reverse of sigma*, at distance Theta(n). Then Lemma 7 has no warm start. The formal definition saves the theorem, because independence conditioned on sigma* is explicit. But the informal presentation overstates the robustness of the model. That is a communication gap, not an internal error.\n\nAnother caveat, minor: the model assumes a single hidden optimal permutation and independent queries. That's standard in the learning-augmented sorting literature, and the authors state it clearly, so I don't count it against them.\n\nBottom line: this is a solid paper for researchers in algorithms with predictions and anyone interested in exact solvability with noisy pairwise information. It deserves a serious referee; I'd be happy to see it accepted after the authors fix the abstract to match Definition 2.","headline":"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.","tokens_in":13961,"tokens_out":1952,"would_cite":true,"duration_ms":19296,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pairwise predictions crack NP-hard permutation problems in polynomial time","keywords":["learning-augmented algorithms","algorithms with predictions","permutation problems","noisy sorting","pairwise comparisons","dynamic programming","decomposition property","c-locality"],"falsifier":"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.","tokens_in":12980,"feed_emoji":"🎯","tokens_out":3252,"duration_ms":33317,"temperature":0.7,"pith_summary":"The paper claims that for any permutation optimization problem whose objective function either decomposes into subproblems or depends only on nearby elements, pairwise predictions about the optimal ordering are enough to solve the problem exactly in polynomial time with high probability. The predictions need only be correct with probability slightly above 1/2, and the algorithm uses only O(n log n) of the possible pairwise queries. If true, this makes several classic NP-hard problems—maximum acyclic subgraph, minimum linear arrangement, single-machine scheduling with precedence constraints, traveling salesman, and keyword auction welfare with externalities—tractable whenever such weak pairwise advice is available.","feed_headline":"Pairwise predictions make NP-hard permutation problems polynomial","feed_subtitle":"With accuracy just over 1/2, pairwise comparison advice turns five classic NP-hard problems exactly solvable in polynomial time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Braverman and Mossel's noisy sorting without resampling algorithm is the starting point and provides the O(n log n)-query, polynomial-time s-optimal solution used in Lemma 7.","marker":"[3]"},{"why":"The journal version of the noisy sorting result, which contains the proof that an s-optimal order is within O(log n) of the hidden permutation.","marker":"[4]"},{"why":"ETH hardness of TSP and other problems is used in the tightness results (Propositions 14 and 15).","marker":"[16]"},{"why":"Karp's reduction establishes that Max Acyclic Subgraph is NP-hard and provides the strong exponential-time hardness needed for the lower bound.","marker":"[17]"},{"why":"Lokshtanov et al.'s superexponential hardness of Permutation Clique is used to show that an O(log n)-position-enhanced problem can remain hard.","marker":"[20]"}],"fun_headline_variants":["Slightly better than random predictions crack NP-hard permutation problems","Pairwise advice with 50%+ accuracy makes NP-hard problems polynomial","A tiny edge in predictions turns NP-hard permutation problems easy","Using noisy pairwise hints to solve NP-hard permutation problems in poly time","Pinpointing NP-hard permutations with just-over-half accurate pairwise hints"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Slightly better than random predictions crack NP-hard permutation problems","Pairwise advice with 50%+ accuracy makes NP-hard problems polynomial","A tiny edge in predictions turns NP-hard permutation problems easy","Using noisy pairwise hints to solve NP-hard permutation problems in poly time","Pinpointing NP-hard permutations with just-over-half accurate pairwise hints"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000684,"raw_usage":{"total_tokens":3010,"prompt_tokens":759,"completion_tokens":2251,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":375,"completion_tokens_details":{"reasoning_tokens":2163}},"tokens_in":375,"tokens_out":2251,"duration_ms":30775,"temperature":1.0,"reasoning_tokens":2163,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T17:34:58.951511+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Noisy sorting without resampling","cited_arxiv_id":null,"evidence_quote":"Braverman and Mossel's noisy sorting without resampling algorithm is the starting point and provides the O(n log n)-query, polynomial-time s-optimal solution used in Lemma 7."},{"cited_title":"Which problems have strongly exponential complexity? J","cited_arxiv_id":null,"evidence_quote":"ETH hardness of TSP and other problems is used in the tightness results (Propositions 14 and 15)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Karp's reduction establishes that Max Acyclic Subgraph is NP-hard and provides the strong exponential-time hardness needed for the lower bound."},{"cited_title":"Slightly superexponential parameterized problems","cited_arxiv_id":null,"evidence_quote":"Lokshtanov et al.'s superexponential hardness of Permutation Clique is used to show that an O(log n)-position-enhanced problem can remain hard."}],"review_version":1}