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.
Title resolution pending
4 Pith papers cite this work, alongside 516 external citations. Polarity classification is still indexing.
4
Pith papers citing it
516
external citations · Crossref
citation-role summary
background 1
citation-polarity summary
years
2026 4verdicts
UNVERDICTED 4roles
background 1polarities
background 1representative citing papers
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.
-
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.