Max Independent Set on twin-width-4 graphs admits no polynomial-time n to the power gamma over (log log n) squared approximation unless ETH fails.
How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs , booktitle =
8 Pith papers cite this work. Polarity classification is still indexing.
8
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
A 1-PLS of cost p implies a t-PLS of cost O(ceil(p/t)) up to log n factors in general graphs and O(ceil(p/t) + log n) in fixed minor-free graphs.
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
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.
Under ETH, approximating parameterized MLD and NCP within a fixed constant factor requires n^Omega(k) time via a direct reduction from Gap-MAXLIN hardness using cover families.
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.
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.
citing papers explorer
-
Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width
Max Independent Set on twin-width-4 graphs admits no polynomial-time n to the power gamma over (log log n) squared approximation unless ETH fails.
-
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
A 1-PLS of cost p implies a t-PLS of cost O(ceil(p/t)) up to log n factors in general graphs and O(ceil(p/t) + log n) in fixed minor-free graphs.
-
Gap-Majority Lemmas in Communication Complexity
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
-
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.
-
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
Under ETH, approximating parameterized MLD and NCP within a fixed constant factor requires n^Omega(k) time via a direct reduction from Gap-MAXLIN hardness using cover families.
-
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.
-
Are controlled unitaries helpful?
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.