CS Paper Radar

Approximate clearing in financial networks with credit default swaps: hardness thresholds, a box algorithm, barriers, and exact solvency at bounded degree

Michal Čertík

cs.CC q-fin.RM ·submitted 2026-10-31 12:00 UTC · v1
theory

Abstract

We study approximate clearing in financial networks with credit default swaps. For weak notions (W) and (I), we prove PPAD-hardness below a threshold approximately $0.2530$ and give a polynomial-time interval algorithm above a threshold approximately $0.2834$. On networks whose CDS writers are solvent ex ante, the corresponding bounds are $(13-\sqrt{153})/4$ and $3-2\sqrt{2}$, approximately $0.1577$ and $0.1716$. The thresholds are sharp for bounded-radius algorithms: for (I) on writer-solvent networks, and for (I) and (W) in general. On non-degenerate networks, (W) and (I) have identical hardness and tractability threshold endpoints. For exact-solvency notion (D), PPAD-hardness holds at every rational error $\varepsilon<1$ on non-degenerate networks. On a restricted unit-notional class, let $d$ be the maximum number of CDS contracts held by a core bank, counted with multiplicity. For rational $\varepsilon\in[1/2,1)$, writing $ρ=(1+\varepsilon)/(1-\varepsilon)$, the problem is polynomial-time solvable when $d<(\lceilρ\rceil+1)ρ$ and PPAD-complete otherwise. At $\varepsilon=1/3$ the boundary is $d=5$ versus $d=6$; below $\varepsilon=1/9$, degree $2$ is already PPAD-complete, while degree $1$ is exactly solvable. These degree results concern (D) and do not close the (W)/(I) approximation windows. We also establish a barrier to Pure-Circuit reductions certified by interval propagation under stated interface and auxiliary-bank restrictions. A finite-precision interval algorithm reduces writer-solvent (I) to point selection in near-stalled boxes; selection is polynomial-time when the residual matrix is symmetric or monotone on each strongly connected component. The general and writer-solvent approximation windows remain open.

Comment
119 pages including references and complete proof appendices. Scientific code and supporting materials: https://doi.org/10.5281/zenodo.23834656

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Inapproximability for Generalized Circuits

cs.GT cs.CC ·2026-10-19 ·Panagiotis Kanellopoulos, Themistoklis Melissourgos
theory similarity 0.63
Abstract

Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a wide range of approximation parameters. We settle this question by establishing a tight threshold at $\varepsilon=1/6$. Specifically, we prove that $\varepsilon$-GCircuit is PPAD-complete for every constant $0<\varepsilon<1/6$, even when restricted to four gate types, and polynomial-time solvable for every constant $\varepsilon\ge1/6$. This closes the gap between the previously known hardness bound of $1/10$ and the polynomial-time solvability bound of $1/2$. We further investigate the relaxation in which a fraction $δ$ of the gates may be violated. We establish polynomial-time solvability of $(\varepsilon,δ)$-GCircuit for every constant $\varepsilon>0$ and $δ>1/5$, and of the fan-out-one formulations of $δ$-Pure-Circuit for every constant $δ>1/8$. These results follow from a decomposition theorem for directed graphs of maximum in-degree two and establish that the PCP-for-PPAD conjecture cannot be true for the aforementioned values of $\varepsilon$ and $δ$, unless PPAD = P. To showcase the contribution of our positive results, we apply them to a variety of problems in algorithmic game theory, including public goods games, financial networks, Bayesian, polymatrix, and graphical games, and obtain improved approximation guarantees.

0.34

Hardness of Online Directed Steiner Network

cs.DS ·2026-09-18 ·Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.63
Abstract

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

0.18

Tight Bounds for Differentially Private Cut Release

cs.DS ·2026-11-14 ·Chenghua Liu, Boning Meng
theory similarity 0.60
Abstract · 24 pages

We give a polynomial-time algorithm for releasing a nonnegative weighted synthetic graph under $(\varepsilon,δ)$-edge differential privacy. Given an $n$-vertex nonnegative weighted graph $G=(V,w_G)$, the output $H=(V,w_H)$ satisfies, with probability at least $1-β$, simultaneously for every $S\subseteq V$, $|w_G(S,V\setminus S)-w_H(S,V\setminus S)| \leγw_G(S,V\setminus S)+O\bigl((n\log n)/(\varepsilonγ)\bigr)$, provided that $γ,\varepsilon,δ,β$ are at least inverse polynomial in $n$. For constant $γ,\varepsilon$ and $δ=β=n^{-10}$, this improves the recently obtained additive error bound of $O(n\log^7 n)$ to $O(n\log n)$. We also prove a matching $Ω(n\log n)$ lower bound. Our algorithm combines degree decomposition with private multiplicative weights, using a degree-sensitive semidefinite oracle to generate update proposals from single Gaussian samples. Each proposal is validated by a noisy check of its exact entropy decrease, and a joint Rényi analysis of sampling and validation avoids additional logarithmic losses.

0.07

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

cs.GT ·2026-10-26 ·Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani
theory similarity 0.60
Abstract

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Under bi-valued utilities, it admits a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-complete for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Assuming the PCP-for-PPAD conjecture, we strengthen the above-stated result to constant additive-error hardness. For the concave extension, we compute an exact equilibrium in strongly polynomial time with two marginal utility slopes common across goods for each buyer and arbitrary rational buyer-good breakpoints. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

0.16

Almost Lossless Transfer for Cuttable Distributed Problems

cs.DS cs.DC ·2026-10-11 ·Wojciech Wawrzyniak
theory similarity 0.59
Abstract · 33 pages, 1 figure, 3 tables, 2 algorithms

We study constant-round LOCAL approximation for additive local vertex-subset minimization problems. Given a $k$-uniform $α$-approximation on a hereditary source class closed under disjoint union, Bonamy, Das, Gavoille, Picavet, Suomela, and Wesolek obtained ratio $α(d+1)+1$ on locally nice target classes of asymptotic dimension $d$. We prove two transfers with ratios $α+1+η$ and $α+η$ for every $η>0$. These bounds require the stronger local niceness assumption at a larger scale that depends on $η$. The first algorithm keeps their repair construction and increases the radius used to detect errors. We average over partitions of the graph to bound the retained cost without the factor $d+1$. These partitions are used only in the analysis. The second algorithm tests several deletion widths around the errors. In each component of the repair zone, it chooses a smallest union of retained choices and an exact repair. Averaging over the widths bounds the cost counted twice and yields ratio $α+η$. Both transfers are deterministic and computable, use arbitrary distinct numerical identifiers, and need no knowledge of the graph size. Their outputs also satisfy local uniformity guarantees. For 2-domination on graphs of bounded Euler genus, the same planar source gives ratio $19$ through the earlier transfer and $6+η$ through ours. For minimum dominating set, our transfer gives ratio $7+\varepsilon$ on graphs formed by attaching a clique of arbitrary size at one vertex of a planar graph, using the source algorithm of Amiri and Siebertz. This class satisfies our target assumptions and allows nonempty error sets. Its Euler genus is unbounded, so their guarantee for graphs of bounded Euler genus does not cover the whole class.

0.27

An EPTAS for Max-Cut on Interval Graphs

cs.DS ·2026-11-11 ·Hani Ahmadzadeh, Morteza Alimi
theory similarity 0.59
Abstract

Max-Cut was shown NP-hard on interval graphs by Adhikary, Bose, Mukherjee, and Roy (SoCG 2021). The best previously known approximation ratio for this class, due to Ahn, DeHaan, Kim, and Lee (APPROX 2025), exceeded the Goemans--Williamson ratio of about $0.878$ by only $10^{-34}$. We give a deterministic efficient polynomial-time approximation scheme (EPTAS): for every $\varepsilon\in(0,1)$, a $(1-\varepsilon)$-approximate cut of an unweighted $n$-vertex interval graph can be found in time $2^{O(\varepsilon^{-2}\log^3(2/\varepsilon))}n^2$. The same guarantee and running time hold for Max-Bisection. An FPTAS is impossible unless $\mathrm{P}=\mathrm{NP}$. Our algorithm rests on a structural theorem: every interval graph with $m$ edges can be turned into an interval graph of clique-width $O(\varepsilon^{-2}\log^2(2/\varepsilon))$ by deleting at most $\varepsilon m$ edges. The construction combines endpoint-rank coordinates, length-dependent rounding, and a shifted dyadic hierarchy. Intervals intersecting cell boundaries at their own scales are isolated at small total edge cost; the interactions of remaining long intervals with smaller subproblems can be summarized by counts. The structural theorem also yields a randomized EPTAS via Lampis's scheme for bounded clique-width; our direct dynamic program is deterministic and handles Max-Bisection. Finally, for every $\varepsilon>0$, it is NP-hard to approximate Max-Cut within $84/85+\varepsilon$ on unweighted chordal graphs, which contain interval graphs. Thus an approximation scheme for Max-Cut on chordal graphs would imply $\mathrm{P}=\mathrm{NP}$.

0.41

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.59
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

A Polynomial-Time Sixth-Power Excluded Grid Theorem

cs.DS ·2026-11-12 ·Mohammad Hajiaghayi
theory similarity 0.59
Abstract

We give a polynomial-time construction for a sixth-power excluded-grid theorem. Every graph whose treewidth is at least $g^6$ times a fixed polylogarithmic factor contains a $g\times g$ grid minor that our randomized algorithm finds with constant probability. The algorithm outputs an explicit minor model, and the exponent in its running time is independent of $g$. This improves the ninth-power existence bound of Chuzhoy and Tan~\cite{CT21} and the $g^{98}$ threshold in the polynomial-time construction of Chekuri and Chuzhoy~\cite{CC16}. Quantitative bounds relating treewidth to grid size are central to bidimensionality, developed by Demaine, Hajiaghayi, and collaborators~\cite{DH05,DH08}. The main ingredient is an asymmetric local routing theorem that uses substantially fewer attachment paths than backbone paths. A balanced recursion preserves connectivity by charging deletions to the boundary of a fixed reference cluster. We construct the smaller attachment sets through a routing hierarchy: either it exposes an accessible well-linked boundary, or its quotient graphs contain the desired grid. These arguments implement cluster splitting using approximate cuts and flow computations. An explicit cut-matching construction and a constructive grid-extraction procedure complete the algorithm. We also give a general packing--covering hypothesis for trees meeting three prescribed terminal sets under which the exponent can be reduced below six. A companion Lean development verifies the new construction, its success guarantee, and the composition of its polynomial running time, using explicit interfaces for the published algorithms and standard finite-data operations.

0.19