{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihovsetsd2ghzlmzggseqthqp5wcbx2tity73d6epzvkezfbfo2b4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mistxmtvve22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.02582v1",
  "publishedAt": "2026-04-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Noah Fleming",
    "Max Hopkins",
    "Yuichi Yoshida"
  ],
  "textContent": "**Authors:** Noah Fleming, Max Hopkins, Yuichi Yoshida\n\nMinimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps between known algorithms and lower bounds. Chang and Li prove an $Ω(\\log n)$-locality lower bound for a constant factor approximation, while Kuhn--Moscibroda--Wattenhofer gave an algorithm beating this bound beyond $\\log Δ$-approximation, along with a weaker lower bound for this degree-dependent setting scaling roughly with $\\min\\\\{\\log Δ/\\log\\log Δ,\\sqrt{\\log n/\\log\\log n}\\\\}$. Unfortunately, this latter bound is weak for small $Δ$, and never recovers the Chang--Li bound, leaving central questions: does $O(\\log Δ)$-approximation require $Ω(\\log n)$ locality, and do such bounds extend beyond LOCAL? In this work, we take a major step toward answering these questions in the non-signaling model, which strictly subsumes the LOCAL, quantum-LOCAL, and bounded-dependence settings. We prove every $O(\\logΔ)$-approximate non-signaling distribution for dominating set requires locality $Ω(\\log n/(\\logΔ\\cdot \\mathrm{poly}\\log\\logΔ))$. Further, we show for some $β\\in (0,1)$, every $O(\\log^βΔ)$-approximate non-signaling distribution requires locality $Ω(\\log n/\\logΔ)$, which combined with the KMW bound yields a degree-independent $Ω(\\sqrt{\\log n/\\log\\log n})$ quantum-LOCAL lower bound for $O(\\log^βΔ)$-approximation algorithms. The proof is based on two new low-soundness sensitivity lower bounds for label cover, one via Impagliazzo--Kabanets--Wigderson-style parallel repetition with degree reduction and one from a sensitivity-preserving reworking of the Dinur--Harsha framework, together with the reductions from label cover to set cover to dominating set and the sensitivity-to-locality transfer theorem of Fleming and Yoshida.",
  "title": "Non-Signaling Locality Lower Bounds for Dominating Set"
}