CS Paper Radar

On the Computational Complexity of Problems: Formalizing Sensitivity to Uncertainty and Parametric Complexity Classes

Yannis Tzitzikas

cs.CC ·submitted 2026-10-04 17:16 UTC · v2
theory

Abstract

Worst-case analysis, the setting of the $P \stackrel{?}{=} NP$ question, measures the cost of a problem as a function of input size alone. Yet problems that are exponential in general often become polynomial, even linear, once a checkable property of the input is known: Partition, for instance, is decidable in linear time on inputs whose elements are all equal. We develop a framework that makes such knowledge an explicit parameter $K$ of complexity statements. Costs are measured for fixed algorithms; we distinguish the promise cost from the guarded cost that also pays for checking $K$, and introduce the residual uncertainty $Ψ(n,K)$, the number of input cells that, together with $K$, determine the input. An Uncertainty Reduction Theorem decomposes the guarded cost into checking $K$, locating and reading the residual information, and solving an explicit reduced problem. The classes $P_\upsilon[K]$ and $NP_\upsilon[K]$ are restrictions to polynomial-time promises, made informative by the coverage of $K$. We show that small $Ψ$ forces sparsity but not tractability, characterize FPT as uniform membership in graded families $P_\upsilon[K_k]$, prove a free-variable threshold for SAT, and show that under the factoring assumption no checkable property of non-negligible coverage makes factoring easy. We relate the framework to promise problems, kernelization, average- and generic-case complexity and beyond-worst-case analysis, illustrate it on Partition, Graph Isomorphism, SAT, Vertex Cover and TSP, and apply it to guarded algorithm dispatch with latency contracts and optimal guard ordering, to solver routing in agentic AI, and to the role of promises in quantum speedups.

Comment
40 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Consistent Submodular Maximization with Full Foresight

cs.DS cs.LG ·2026-11-04 ·Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard +2 more
theory similarity 0.64
Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

0.44

The Gap Between Average-Case and Worst-Case Complexity

cs.CC ·2026-10-13 ·Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
publishedtheory similarity 0.63
Abstract

Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.

0.28

Robust Approximation and the Arity Barrier at Width Two

cs.CC ·2026-09-29 ·Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
theory similarity 0.61
Abstract

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.

0.44

Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs

cs.CC ·2026-10-21 ·Inhyuk Park, Chenglin Fan
theory similarity 0.61
Abstract · The abstract is shortened due to the length limit of arXiv

We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier making at most $b$ queries. This improves the length $\tilde O(T+b^2)$ of Zeilberger, O'Connor, Gur and Spooner (2026), who observed that Dinur's gap amplification preserves zero knowledge. The simulator runs in expected polynomial time (or in strict polynomial time, with a failure symbol or with negligible statistical error). For $b\le T$ the length is $T\cdot\mathrm{polylog}\,T$, the form of the shortest known constant-query PCPs without zero knowledge. Unless NP $\subseteq$ BPP, the dependence on $b$ is optimal up to the polylogarithmic factor for polynomial-time simulators: zero knowledge is free up to linear query bounds. Zero-knowledge interactive oracle proofs achieved length $\tilde O(T+b)$ in 2016-17; we obtain it for PCPs. Gur, O'Connor and Spooner (STOC 2025) asked whether NP has such PCPs of quasilinear length (their Open Problem 1). This paper answers it for every polynomial query bound, with the simulators above in place of a strict polynomial-time perfect simulator. The proofs were developed with extensive AI assistance and have been checked by the authors. We mask the Reed-Solomon proof of proximity of Ben-Sasson and Sudan at every node of its recursion. By a locator lemma, at every node, whatever $k$ of its proof symbols reveal about its input is determined by $O(k)$ input values. We prove it with the coprime-order argument of Bafna and Vyas (2026); our treatment of domain points is new. Dinur's gap amplification gives constant query complexity. The query count and the polylogarithmic exponent are absolute but very large.

0.10

Tracking a Small Set of Experts in Online Convex Optimization

cs.LG math.OCstat.ML ·2026-10-14 ·Angelos Assos, Anand Brahmbhatt, Elad Hazan
similarity 0.60
Abstract

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.

0.19

The Information Complexity of Decision Trees

cs.CC ·2026-09-10 ·Avantika Agarwal, Shalev Ben-David, Eric Blais
theory similarity 0.60
Abstract

We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

0.19

Descriptive Complexity in Lean: Completeness by First-Order Reductions

cs.LO cs.CC ·2026-09-16 ·Pierre Senellart, Anton Gnatenko
theorycode/data similarity 0.60
Abstract · 25 pages. Library available at https://github.com/PierreSenellart/descriptive-complexity

We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.

0.47

The Complexity of Choosing Parity Projections

cs.CC ·2026-10-30 ·Karthik Sheshadri, Nicholas Smirnov
theory similarity 0.60
Abstract

Cube attacks in cryptanalysis seek small sets of Boolean variables (cubes) whose parity sum is constant. We study the bounded constant derivative problem introduced by Smirnov (2026), which seeks a smallest cube with sum 1, and its sum-0 analogue. Despite their similarity, the problems differ sharply in parameterized complexity: the sum-1 problem admits a $2^{O(k^2)}\operatorname{poly}(N)$-time algorithm, where $k$ is cube size, whereas the sum-0 problem is not fixed-parameter tractable unless $\mathrm{FPT}=\mathrm{W}[1]$. Without a bound on cube size, both problems are $Σ_2^{\oplus\mathrm{P}}$-complete and NP-hard to approximate within $N^{1-\varepsilon}$ for every fixed $0<\varepsilon<1$. Our hardness proofs use a crown construction that embeds maximal monomials of parity-projected circuits into positive 2CNF. This yields completeness and inapproximability results, as well as a dichotomy for Boolean constraint languages of arity at most two: the bounded constant derivative problem is in P when all relations are affine and $Σ_2^{\oplus\mathrm{P}}$-complete otherwise. We also give algorithms parameterized by the number of quadratic rounds, treewidth, or ordered branching-program width, with lower bounds for the first two unless $\mathrm{NP}\subseteq\mathrm{SUBEXP}$. The treewidth lower bound holds for circuits; the case of 2CNF remains open.

0.23