CS Paper Radar

Approximation and Hardness for the Data Validation Problem

Antoine Tinguely, G. Wessel van der Heijden

cs.DS ·submitted 2026-11-04 16:50 UTC · v1

Abstract

Finnah, Gönsch and Otto [Eur. J. Oper. Res. 2025] recently introduced the Data Validation Problem (DVP): Given a transitive directed acyclic graph $G$ on $n$ vertices (resp. tasks) and $m$ edges (resp. precedences) and a probing budget, a policy can successively pay a probing fee and probe an edge in $G$ as long as the total probing fees do not exceed the budget. If a probe succeeds, the targeted edge $e$ is removed from $G$ and we receive a reward; if the probe fails, the edge stays in $G$ and cannot be probed again. We seek a policy with maximum expected cumulative reward. Crucially, $G$ must stay transitive throughout the probing process, so a policy can only challenge the precedence between consecutive tasks, that is, only probe edges in the transitive reduction of the current precedence graph. We show that DVP is strongly NP-hard and W[1]-hard with the probing budget $T$ as a parameter, even in the deterministic case (when every probe has probability $0$ or $1$ to succeed) and with unit probing costs and rewards. For the same setting, we give an approximation-preserving reduction from the Densest $k$-Subgraph (D$k$S) Problem, with the consequence that there is no polynomial-time $2^{(\log n)^{1-δ}}$-approximation algorithm and no FPT $\sqrt{T}$-approximation algorithm for DVP, assuming the Almost-Exponential Time Hypothesis and the Strongish Planted Clique Hypothesis, respectively. We also present the first known policies with provable worst-case guarantees for DVP, namely an $m$-approximation algorithm for instances with uniform probabilities and probing costs, a $2T/p_{\min}^T$-approximation algorithm for general instances, where $p_{\min}$ is the minimum probing success probability, and an exact FPT algorithm on tournament graphs, in the deterministic setting.

Closest papers

Nearest neighbours by meaning across the whole index.

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

cs.AI ·2026-09-06 ·Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen +1 more
benchmarktheory similarity 0.62
Abstract

Bounded-suboptimal search seeks a solution within a factor $w$ of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold $w f_{\min}$, but its deterministic policy may leave $f_{\min}$ unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability $p$ and expands a minimum-$f$ OPEN node with probability $1-p$. The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple $w$ and $p$ values. Across these benchmarks, the largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90\% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.

0.20

What Makes a Terminal-Bench Task Hard? Separating Genuine Hardness from Fake-Hardness on an Adjudicated Agentic Corpus

cs.LG cs.AI ·2026-09-20 ·Edward Lue Chee Lip, Boden Moraski, Tim Knappe, Lang Xiong, Sarvesh Gharat +2 more
similarity 0.62
Abstract

Frontier benchmarks need tasks that current models cannot solve. But a task that no model solves is not automatically a hard task. The same zero pass rate can come from a real capability gap, but it can also come from missing context, a broken reference solution, infrastructure failure, or a verifier that can be bypassed. In this paper, we study this issue using a frozen Terminal-Bench 3 / Frontier-Bench 0.1 production record with 1,081 pull requests, 639 scored tasks, 28,801 trials, and $105,933 in logged agent spend. We ask what an all-fail task actually certifies. For the 125 tasks with no honest pass, we combine task artifacts, reference-solution runs, empty-solution controls, adversarial trials, trajectories, telemetry, and review records, and apply an ordered validity screen. Only 78 of the 125 tasks survive as certified-unsolved candidates. The remaining tasks include 14 with broken oracles, 8 dominated by infrastructure failures, 4 that are only passable through verifier bypasses, and 21 whose solvability is not certified by the available evidence. Thus, lack of saturation and genuine difficulty are not the same thing. The certified-unsolved label is also narrow: it means that the authored route passed, infrastructure did not dominate, no strict bypass was observed, and all evaluated agents failed. It does not prove intrinsic hardness, verifier completeness, or failure at the intended capability. We further analyze rejected submissions and passing tasks to show that pass rate alone cannot explain why a task is difficult. Overall, our results suggest that frontier benchmarks should report the evidence behind their all-fail tasks before using them as capability claims.

0.19

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

cs.DS ·2026-09-29 ·Prashanti Anderson, Peter Manohar, Jeff Xu
similarity 0.61
Abstract · 21 pages

A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.

0.47

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

cs.AI cs.IT ·2026-09-24 ·Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu +3 more
benchmarkhot direction similarity 0.61
Abstract

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or episodes. For fixed $L \ge 3$ and $0 < α\le 1/12$, the optimal expected width on the worst pure cohort is $Θ_{α,L}([M(t+1)]^{-1/2})$ when every task is observed and $Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})$ when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0\% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6\%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

0.58

Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model

cs.DS ·2026-09-29 ·Dani Dorfman, Simon Döring, Martin G. Herold, Danupon Nanongkai, Daniel Neuen +2 more
top venue similarity 0.60
Abstract · Accepted at FOCS 2026

If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for graph problems called algorithms with isomorphic priors. Solving a graph problem $Π$ in this model involves two phases: (i) The preprocessing phase quickly analyzes prior graphs $G_1, ..., G_k$ along with the (previously computed) exact optimal values OPT$(G_i)$. (ii) Subsequently, given a new graph H, a fast query phase must either (a) output the exact solution OPT(H), or (b) correctly report that H is not isomorphic to any $G_i$. Can we avoid computing OPT(H) from scratch when H is isomorphic to some $G_i$? We show that this is the case for a number of problems; for many others, we establish conditional lower bounds. $\textbf{(1)}$ Some NP-hard problems, including Constrained Shortest Path and $\ell_p$-Shortest Path and Constrained Spanning Tree, admit polynomial preprocessing and query times in our model. In contrast, almost all of Karp's 21 NP-complete problems and $(2-\varepsilon)$-approximate $k$-Center, for every fixed $\varepsilon>0$, admit no such algorithms unless Graph Isomorphism (GI) is in P, even with O(1) priors. $\textbf{(2)}$ In contrast to conditional $n^{3-o(1)}$ fine-grained lower bounds, our framework achieves an $O(n^ω)$ query time for Negative Triangle and a near-linear query time for Replacement Path. It also achieves near-linear query time for Maximum Flow. $\textbf{(3)}$ While it remains a major open problem whether infinite-duration games (Paritiy Game, Mean Payoff Game, Energy Game, and Stochastic Game) admit polynomial-time algorithms, they can be easily solved in near-linear time within our model. Our proofs rely on a simple combination of existing tools and are accessible to readers without specialized background.

0.49

Solver-Admitted Metamorphic Testing of Learned Network Optimization Surrogates

cs.AI cs.LG ·2026-11-06 ·Vineet Jagadeesan Nair, Stephen Peng, Arun Ravindran
similarity 0.59
Abstract

Equivalent encodings of an optimization problem can produce different learned predictions. Interpreting these differences requires accounting for numerical error and multiple optima. We construct metamorphic tests for optimization solver surrogates with explicit eligibility conditions, output alignment, and numerical thresholds. Reference-solver agreement and independent constraint checks determine which sampled pairs enter the audit. We study alternating-current optimal power flow (AC-OPF), the traveling salesman problem (TSP), the capacitated vehicle routing problem (CVRP), and maximum independent set (MIS). Across five grids, GridSFM-Open violates each of 13 relations on at least one grid, and 12 by more than twice the threshold. Randomly initialized copies of the grid models fail nearly the same relations, so the failures do not require training. Source patches and input canonicalization remove selected discrepancies, but no intervention establishes preserved accuracy and feasibility within the declared margin on every grid. In routing, Policy Optimization with Multiple Optima (POMO) has a single-pass rotation/reflection violation rate that rises from 12.7% to 89.5% between 20 and 100 cities. Graph-Based Diffusion Solvers for Combinatorial Optimization (DIFUSCO) violates the MIS disjoint-union relation on 35.6% of draws. Post hoc normalization within connected components removes these violations on the tested graphs. These findings support reporting metamorphic consistency alongside optimality, feasibility, and accuracy, and validating repair quality separately from consistency.

0.29

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

cs.LG eess.SYmath.OCstat.ML ·2026-11-02 ·Ridham Patel
publishedtheory similarity 0.59
Abstract · Accepted at NeurIPS 2026 FMTS Workshop

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$-Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$. This barrier is caused by the budget rather than by a volatile environment: for fixed $D$, it applies when $P_T = o(T)$, where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$. Thus the critical movement scale is $D+P_T$: linear regret is unavoidable below a sufficiently small constant multiple of $P_T$, while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.

0.32

Settling PROPm and PROPavg in Graphical Resource Allocation

cs.GT ·2026-10-07 ·Bo Li, Ankang Sun, Ruijie Wang
publishedtheory similarity 0.58
Abstract · Full version of a paper to appear in WINE 2026. V2 includes an extended related work section

We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been proved that PROP1 orientations always exist and PROPx orientations may not, but it has remained open whether the intermediate relaxations PROPm and PROPavg (both can be satisfied without graphical constraints) can always be satisfied. In this paper, we resolve this gap. We prove that PROPm orientations always exist for goods on multigraphs and can be computed efficiently. The guarantee extends to chores and a mixture of goods and chores. In sharp contrast, we show that PROPavg orientations need not exist, even for simple graphs with binary valuations, and that deciding their existence is NP-complete. We further quantify the efficiency loss of PROPm: for goods, the price of PROPm is exactly $2$, which is one of the few settings where a constant bound on the price of fairness can be obtained. We complement these results with hardness results for welfare optimization under PROPm and for the existence of orientations that are simultaneously PROPm and Pareto optimal.

0.25