This work charts a nuanced complexity landscape for diameter computation on 2D intersection graphs, delivering new subquadratic algorithms for some object types and diameter values while proving hardness for others under fine-grained assumptions.
On the density of families of sets
7 Pith papers cite this work, alongside 516 external citations. Polarity classification is still indexing.
7
Pith papers citing it
516
external citations · Crossref
citation-role summary
background 1
citation-polarity summary
years
2026 7verdicts
UNVERDICTED 7roles
background 1polarities
background 1representative citing papers
Constant-factor LP-based approximation for Max Dist-2 Independent Set (and Min Dominating Set) in bounded radius-2 merge-width graphs, with the domination-to-2-independence ratio shown bounded and tight for radius-1.
Presents polynomial-time algorithms for 2D forecasting with Õ(√(kT)) swap regret and extensions to higher dimensions with Õ(d√(kT)) bounds, improving prior regret and runtime results.
cgFOC admits computable VC-dimension bounds on nowhere dense structures and efficient algorithms for query answering and PAC learning on locally bounded expansion classes, but a minor extension is intractable on trees.
Explicit families of CNF formulas exist such that tree-like semantic Frege refutations with line size s(n) require superpolynomial length for most formulas in the family, for s(n) in a broad range from nearly quadratic to subexponential in n.
Local tensor-train surrogates approximate quantum machine learning models via Taylor polynomials and tensor networks, delivering polynomial parameter scaling and explicit generalization bounds controlled by patch radius.
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
citing papers explorer
-
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
This work charts a nuanced complexity landscape for diameter computation on 2D intersection graphs, delivering new subquadratic algorithms for some object types and diameter values while proving hardness for others under fine-grained assumptions.
-
Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width
Constant-factor LP-based approximation for Max Dist-2 Independent Set (and Min Dominating Set) in bounded radius-2 merge-width graphs, with the domination-to-2-independence ratio shown bounded and tight for radius-1.
-
Improved Multi-Dimensional Forecasting for Swap Regret
Presents polynomial-time algorithms for 2D forecasting with Õ(√(kT)) swap regret and extensions to higher dimensions with Õ(d√(kT)) bounds, improving prior regret and runtime results.
-
Complexity of Clique-Guarded First-Order Logic with Counting
cgFOC admits computable VC-dimension bounds on nowhere dense structures and efficient algorithms for query answering and PAC learning on locally bounded expansion classes, but a minor extension is intractable on trees.
-
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
Explicit families of CNF formulas exist such that tree-like semantic Frege refutations with line size s(n) require superpolynomial length for most formulas in the family, for s(n) in a broad range from nearly quadratic to subexponential in n.
-
Local tensor-train surrogates for quantum learning models
Local tensor-train surrogates approximate quantum machine learning models via Taylor polynomials and tensor networks, delivering polynomial parameter scaling and explicit generalization bounds controlled by patch radius.
-
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.