pith. sign in

arxiv: 2604.02582 · v1 · submitted 2026-04-02 · 💻 cs.DS

Non-Signaling Locality Lower Bounds for Dominating Set

Noah Fleming , Max Hopkins , Yuichi Yoshida This is my paper

Pith reviewed 2026-05-13 19:58 UTC · model grok-4.3

classification 💻 cs.DS
keywords dominating setnon-signaling localitylower boundslabel coverparallel repetitiondistributed algorithmsapproximation algorithmssensitivity bounds
0
0 comments X

The pith

Every O(log Δ)-approximate non-signaling distribution for minimum dominating set requires locality Ω(log n / (log Δ ⋅ polyloglog Δ)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves new lower bounds on the locality required for approximate solutions to minimum dominating set in the non-signaling model. This model strictly contains the classical LOCAL model as well as quantum-LOCAL and bounded-dependence variants. The authors first obtain low-soundness sensitivity lower bounds for label cover, one via parallel repetition with degree reduction and one via a reworked Dinur-Harsha framework. These bounds are then transferred through standard reductions to set cover and then to dominating set using the sensitivity-to-locality theorem. The resulting statements close the gap between the Chang-Li Ω(log n) bound for constant-factor approximation and the weaker Kuhn-Moscibroda-Wattenhofer bounds that depend on maximum degree Δ.

Core claim

We prove that every O(log Δ)-approximate non-signaling distribution for dominating set requires locality Ω(log n/(log Δ ⋅ polyloglog Δ)). Further, for some β ∈ (0,1), every O(log^β Δ)-approximate non-signaling distribution requires locality Ω(log n/log Δ). These statements follow from two new low-soundness sensitivity lower bounds for label cover, combined with the reductions from label cover to set cover to dominating set and the sensitivity-to-locality transfer theorem.

What carries the argument

Sensitivity-to-locality transfer theorem applied to low-soundness sensitivity lower bounds for label cover obtained via parallel repetition and a sensitivity-preserving Dinur-Harsha reworking.

If this is right

  • The bound improves the Kuhn-Moscibroda-Wattenhofer locality lower bound for O(log Δ)-approximation.
  • For some β < 1 the Ω(log n / log Δ) bound combines with the existing KMW algorithm to give a degree-independent Ω(√(log n / log log n)) quantum-LOCAL lower bound.
  • The same sensitivity lower bounds for label cover apply to any problem that reduces from label cover while preserving the non-signaling property.
  • The results hold in every model strictly weaker than non-signaling, including quantum-LOCAL and bounded-dependence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar locality barriers are likely to appear for other local covering problems once their label-cover reductions are examined at low soundness.
  • The parallel-repetition and Dinur-Harsha techniques may yield low-soundness sensitivity bounds for additional CSPs that currently lack non-signaling lower bounds.
  • If the transfer theorem extends to other covering problems, the same quantitative gap between classical and non-signaling models would close for set cover as well.

Load-bearing premise

The reductions from label cover to set cover to dominating set preserve the relevant approximation and locality parameters without introducing additional soundness loss.

What would settle it

An explicit construction of an O(log Δ)-approximate non-signaling distribution for dominating set whose locality is o(log n / (log Δ ⋅ polyloglog Δ)) would falsify the primary claim.

Figures

Figures reproduced from arXiv: 2604.02582 by Max Hopkins, Noah Fleming, Yuichi Yoshida.

Figure 1
Figure 1. Figure 1: Before and after applying degree-reduction on a right vertex [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The stage-0 left-predicate label cover instance. In the label-cover instance, a left vertex u = (Ω, τ ) will carry two kinds of information: the restriction of the outer algebraic objects to the object Ω, and the auxiliary-answer string from one accepted local view certifying the local evaluation at the distinguished point z of Ω. The inner edges simply project the slots of that auxiliary-answer string to … view at source ↗
Figure 3
Figure 3. Figure 3: The transformation of the alphabet reduction procedure [PITH_FULL_IMAGE:figures/full_fig_p051_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The conversion of a vertex v and its neighborhood under composition. instances with local description complexity at most S I = [PITH_FULL_IMAGE:figures/full_fig_p059_4.png] view at source ↗
read the original abstract

Minimum 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 $\Omega(\log n)$-locality lower bound for a constant factor approximation, while Kuhn--Moscibroda--Wattenhofer gave an algorithm beating this bound beyond $\log \Delta$-approximation, along with a weaker lower bound for this degree-dependent setting scaling roughly with $\min\{\log \Delta/\log\log \Delta,\sqrt{\log n/\log\log n}\}$. Unfortunately, this latter bound is weak for small $\Delta$, and never recovers the Chang--Li bound, leaving central questions: does $O(\log \Delta)$-approximation require $\Omega(\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\Delta)$-approximate non-signaling distribution for dominating set requires locality $\Omega(\log n/(\log\Delta \cdot \mathrm{poly}\log\log\Delta))$. Further, we show for some $\beta \in (0,1)$, every $O(\log^\beta \Delta)$-approximate non-signaling distribution requires locality $\Omega(\log n/\log\Delta)$, which combined with the KMW bound yields a degree-independent $\Omega(\sqrt{\log n/\log\log n})$ quantum-LOCAL lower bound for $O(\log^\beta\Delta)$-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript claims to prove that every O(log Δ)-approximate non-signaling distribution for minimum dominating set requires locality Ω(log n / (log Δ ⋅ polyloglog Δ)). It further claims that for some β ∈ (0,1), every O(log^β Δ)-approximate non-signaling distribution requires locality Ω(log n / log Δ). These bounds are derived from new low-soundness sensitivity lower bounds for label cover (via IKW-style parallel repetition with degree reduction and a sensitivity-preserving reworking of the Dinur-Harsha framework), composed with the standard label-cover → set-cover → dominating-set reductions, and transferred to non-signaling locality via the Fleming-Yoshida theorem. The results also yield a degree-independent Ω(√(log n / log log n)) quantum-LOCAL lower bound for O(log^β Δ)-approximations.

Significance. If the central claims hold, the paper meaningfully advances the understanding of locality lower bounds for approximate dominating set beyond the LOCAL model, into the strictly stronger non-signaling setting that subsumes quantum-LOCAL and bounded-dependence models. It tightens the gap left by Chang-Li (Ω(log n) for constant-factor approximations) and Kuhn-Moscibroda-Wattenhofer (weaker degree-dependent bounds), while introducing technically novel low-soundness sensitivity constructions for label cover that may apply more broadly. The combination with existing upper bounds produces a concrete quantum-LOCAL consequence.

major comments (2)
  1. [Application of Fleming-Yoshida theorem] The proof of the main locality bounds (Abstract and the proof overview) applies the Fleming-Yoshida sensitivity-to-locality transfer theorem to the new low-soundness sensitivity lower bounds. The manuscript must explicitly verify that the achieved soundness (arbitrarily close to 1) and the dependence structure after the degree-reduction step in parallel repetition satisfy the theorem's hypotheses (typically requiring a constant soundness gap and bounded dependence); if these conditions fail, the claimed exponents Ω(log n / (log Δ ⋅ polyloglog Δ)) and Ω(log n / log Δ) may not hold.
  2. [Low-soundness sensitivity bounds for label cover] The low-soundness sensitivity lower bounds for label cover (via IKW-style parallel repetition with degree reduction and the reworked Dinur-Harsha framework) are load-bearing for both main theorems. The manuscript should provide a self-contained argument that sensitivity is preserved under the degree reduction and that the resulting soundness parameter does not introduce additional polyloglog factors that would weaken the final locality statements.
minor comments (3)
  1. [Abstract] In the Abstract, the notation 'poly log log Δ' should be expanded to an explicit form such as (log log Δ)^O(1) and the hidden constant clarified if possible.
  2. [Introduction] The discussion of prior work (Introduction) would benefit from precise page or theorem citations to the Chang-Li Ω(log n) bound and the exact KMW locality expression min{log Δ / log log Δ, √(log n / log log n)}.
  3. [Notation and statements] Ensure uniform notation for the maximum degree (Δ) and number of vertices (n) across all sections and the statement of the quantum-LOCAL corollary.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where additional explicit verification would strengthen the presentation. We address both major comments below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Application of Fleming-Yoshida theorem] The proof of the main locality bounds (Abstract and the proof overview) applies the Fleming-Yoshida sensitivity-to-locality transfer theorem to the new low-soundness sensitivity lower bounds. The manuscript must explicitly verify that the achieved soundness (arbitrarily close to 1) and the dependence structure after the degree-reduction step in parallel repetition satisfy the theorem's hypotheses (typically requiring a constant soundness gap and bounded dependence); if these conditions fail, the claimed exponents Ω(log n / (log Δ ⋅ polyloglog Δ)) and Ω(log n / log Δ) may not hold.

    Authors: We agree that an explicit verification improves clarity and rigor. In the revised manuscript we will add a dedicated subsection (in the proof overview and before the main theorems) that directly checks the hypotheses of the Fleming-Yoshida theorem. Specifically, we will confirm that the soundness gap remains a fixed positive constant (independent of n and Δ) after the low-soundness construction, and that the dependence structure produced by the degree-reduction step in the IKW-style parallel repetition is bounded by a constant. These verifications ensure that the transfer theorem applies directly and that the stated locality exponents hold without hidden factors. revision: yes

  2. Referee: [Low-soundness sensitivity bounds for label cover] The low-soundness sensitivity lower bounds for label cover (via IKW-style parallel repetition with degree reduction and the reworked Dinur-Harsha framework) are load-bearing for both main theorems. The manuscript should provide a self-contained argument that sensitivity is preserved under the degree reduction and that the resulting soundness parameter does not introduce additional polyloglog factors that would weaken the final locality statements.

    Authors: We will expand the technical sections on the label-cover sensitivity bounds to include a self-contained argument establishing preservation of sensitivity under degree reduction. We will also show explicitly that the soundness parameter achieved by the reworked Dinur-Harsha framework introduces no extra polyloglog factors beyond those already present in the final locality expressions. These arguments will be presented in a new appendix (or expanded main-text subsection) so that the reader can verify the claims without external references. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent new constructions

full rationale

The paper's chain consists of (1) novel low-soundness sensitivity lower bounds for label cover obtained via IKW-style parallel repetition with degree reduction and a sensitivity-preserving reworking of Dinur-Harsha, (2) standard label-cover to set-cover to dominating-set reductions, and (3) application of the cited Fleming-Yoshida sensitivity-to-locality transfer theorem. No equation or claim reduces by construction to a fitted parameter, self-definition, or unverified self-citation chain; the new sensitivity bounds supply independent content that is then transferred. The self-citation is normal and not load-bearing in a circular sense because the theorem is invoked as an external mathematical fact whose hypotheses the paper asserts are met by its constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

Proof relies on standard mathematical properties of parallel repetition and label cover plus the cited sensitivity-to-locality transfer; no free parameters or invented entities are visible from the abstract.

axioms (4)
  • standard math Properties of Impagliazzo-Kabanets-Wigderson-style parallel repetition with degree reduction for label cover
    Used to obtain one of the two new low-soundness sensitivity lower bounds.
  • standard math Sensitivity-preserving reworking of the Dinur-Harsha framework
    Basis for the second sensitivity lower bound.
  • domain assumption Reductions from label cover to set cover to dominating set
    Standard in the field and invoked to transfer sensitivity bounds to dominating set.
  • domain assumption Sensitivity-to-locality transfer theorem of Fleming and Yoshida
    Directly used to convert sensitivity lower bounds into locality lower bounds.

pith-pipeline@v0.9.0 · 5683 in / 1616 out tokens · 41806 ms · 2026-05-13T19:58:56.906332+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages

  1. [1]

    Aamand, M

    A. Aamand, M. Aliakbarpour, J. Y . Chen, S. Narayanan, and S. Silwal. On the structure of replicable hypothesis testers. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5771–5823, 2026

    work page 2026

  2. [2]

    Akbari, X

    A. Akbari, X. Coiteux-Roy, F. d’Amore, F. Le Gall, H. Lievonen, D. Melnyk, A. Modanese, S. Pai, M.-O. Renou, V . Rozhoˇn, et al. Online locality meets distributed quantum computing. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1295–1306, 2025

    work page 2025

  3. [3]

    N. Alon. Explicit expanders of every degree and size.Combinatorica, 41(4):447–463, 2021

    work page 2021

  4. [4]

    Arfaoui and P

    H. Arfaoui and P. Fraigniaud. What can be computed without communications?ACM SIGACT News, 45(3):82–104, 2014

    work page 2014

  5. [5]

    Bafna, N

    M. Bafna, N. Lifshitz, and D. Minzer. Constant degree direct product testers with small soundness. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 862–869, 2024

    work page 2024

  6. [6]

    Bafna and D

    M. Bafna and D. Minzer. Characterizing direct product testing via coboundary expansion. InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1978–1989, 2024

    work page 1978

  7. [7]

    Bafna, D

    M. Bafna, D. Minzer, and N. Vyas. Quasi-linear size PCPs with small soundness from HDX. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 45–53, 2025. 109

    work page 2025

  8. [8]

    Balliu, C

    A. Balliu, C. Coupette, A. Cruciani, F. d’Amore, M. Equi, H. Lievonen, A. Modanese, D. Olivetti, and J. Suomela. New limits on distributed quantum advantage: Dequantizing linear programs. In International Symposium on Distributed Computing, pages 1–22. Schloss Dagstuhl-Leibniz-Zentrum f¨ur Informatik, 2025

    work page 2025

  9. [9]

    M. Bun, M. Gaboardi, M. Hopkins, R. Impagliazzo, R. Lei, T. Pitassi, J. Sorrell, and S. Sivakumar. Stability is stable: Connections between replicability, privacy, and adaptive generalization. InPro- ceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 520–527, 2023

    work page 2023

  10. [10]

    Chang and Z

    Y .-J. Chang and Z. Li. The complexity of distributed approximation of packing and covering integer linear programs. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 32–43, 2023

    work page 2023

  11. [11]

    Chleb ´ık and J

    M. Chleb ´ık and J. Chleb´ıkov´a. Approximation hardness of dominating set problems in bounded degree graphs.Information and Computation, 206(11):1264–1275, 2008

    work page 2008

  12. [12]

    Coiteux-Roy, F

    X. Coiteux-Roy, F. d’Amore, R. Gajjala, F. Kuhn, F. Le Gall, H. Lievonen, A. Modanese, M.-O. Renou, G. Schmid, and J. Suomela. No distributed quantum advantage for approximate graph coloring. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1901–1910, 2024

    work page 1901

  13. [13]

    Coupette and C

    C. Coupette and C. Lenzen. A breezing proof of the KMW bound. InProceedings of the Symposium on Simplicity in Algorithms (SOSA), pages 184–195, 2021

    work page 2021

  14. [14]

    Diakonikolas, J

    I. Diakonikolas, J. Gao, D. Kane, S. Liu, and C. Ye. Replicable distribution testing.Advances in Neural Information Processing Systems, 38, 2025

    work page 2025

  15. [15]

    Dikstein and I

    Y . Dikstein and I. Dinur. Agreement theorems for high dimensional expanders in the low acceptance regime: The role of covers. InProceedings of the 56th Annual ACM Symposium on Theory of Com- puting (STOC), pages 1967–1977, 2024

    work page 1967

  16. [16]

    Dikstein and I

    Y . Dikstein and I. Dinur. Swap cosystolic expansion. InProceedings of the 56th Annual ACM Sympo- sium on Theory of Computing (STOC), pages 1956–1966, 2024

    work page 1956

  17. [17]

    Dikstein, I

    Y . Dikstein, I. Dinur, and A. Lubotzky. Low acceptance agreement tests via bounded-degree symplectic HDXs. InProceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 826–861, 2024

    work page 2024

  18. [18]

    Dikstein and M

    Y . Dikstein and M. Hopkins. Chernoff bounds and reverse hypercontractivity on HDX. InProceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 870–919, 2024

    work page 2024

  19. [19]

    Composition of low-error 2-query pcps using decodable pcps.SIAM Journal on Computing, 42(6):2452–2486, 2013

    Y . Dikstein, M. Hopkins, R. Impagliazzo, and T. Pitassi. High rate efficient local list decoding from hdx.arXiv preprint arXiv:2601.22535, 2026

    work page arXiv 2026

  20. [20]

    Dinur and P

    I. Dinur and P. Harsha. Composition of low-error 2-query PCPs using decodable PCPs.SIAM Journal on Computing, 42(6):2452–2486, 2013

    work page 2013

  21. [21]

    Dinur and I

    I. Dinur and I. Livni Navon. Exponentially small soundness for the direct product z-test.Theory of Computing, 19(1):1–56, 2023. 110

    work page 2023

  22. [22]

    Dinur and O

    I. Dinur and O. Meir. Derandomized parallel repetition via structured pcps.computational complexity, 20(2):207–327, 2011

    work page 2011

  23. [23]

    M. Dory, M. Ghaffari, and S. Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 292–300, 2022

    work page 2022

  24. [24]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. InTheory of cryptography conference, pages 265–284. Springer, 2006

    work page 2006

  25. [25]

    Eaton, M

    E. Eaton, M. Hussing, M. Kearns, and J. Sorrell. Replicable reinforcement learning.Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  26. [26]

    Ebbens and Y

    M. Ebbens and Y . Yoshida. Average sensitivity of geometric algorithms. In17th Innovations in Theoretical Computer Science Conference (ITCS 2026), pages 53–1, 2026

    work page 2026

  27. [27]

    U. Feige. A threshold oflnnfor approximating set cover.Journal of the ACM, 45(4):634–652, 1998

    work page 1998

  28. [28]

    Fleming and Y

    N. Fleming and Y . Yoshida. Sensitivity lower bounds for approximation algorithms. In K. G. Larsen and B. Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 4043–4076. SIAM, 2026

    work page 2026

  29. [29]

    Gavoille, A

    C. Gavoille, A. Kosowski, and M. Markiewicz. What can be observed locally? round-based models for quantum distributed computing. InProceedings of the International Symposium on Distributed Computing (DISC), pages 243–257, 2009

    work page 2009

  30. [30]

    Ghaffari, F

    M. Ghaffari, F. Kuhn, and Y . Maus. On the complexity of local distributed graph problems. InPro- ceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 784–797, 2017

    work page 2017

  31. [31]

    Hara and Y

    S. Hara and Y . Yoshida. Average sensitivity of decision tree learning. InProceedings of the 11th International Conference on Learning Representations (ICLR), 2023

    work page 2023

  32. [32]

    P. Harsha. Limits of approximation algorithms: PCPs and Unique Games. Technical report, Tata Institute of Fundamental Research, 2010

    work page 2010

  33. [33]

    H ˚astad

    J. H ˚astad. Some optimal inapproximability results.Journal of the ACM, 48(4):798–859, 2001

    work page 2001

  34. [34]

    A. E. Holroyd, O. Schramm, and D. B. Wilson. Finitary coloring.The Annals of Probability, pages 2867–2898, 2017

    work page 2017

  35. [35]

    Hopkins, R

    M. Hopkins, R. Impagliazzo, D. Kane, S. Liu, and C. Ye. Replicability in high dimensional statistics. InProceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1–8, 2024

    work page 2024

  36. [36]

    arXiv preprint arXiv:2507.11926 , year=

    M. Hopkins, S. Liu, C. Ye, and Y . Yoshida. From generative to episodic: Sample-efficient replicable reinforcement learning.arXiv preprint arXiv:2507.11926, 2025

    work page arXiv 2025

  37. [37]

    Hopkins and S

    M. Hopkins and S. Moran. The role of randomness in stability. InProceedings of the 42nd Interna- tional Conference on Machine Learning (ICML), 2025

    work page 2025

  38. [38]

    Impagliazzo, V

    R. Impagliazzo, V . Kabanets, and A. Wigderson. New direct-product testers and 2-query pcps.SIAM Journal on Computing, 41(6):1722–1768, 2012. 111

    work page 2012

  39. [39]

    Impagliazzo, R

    R. Impagliazzo, R. Lei, T. Pitassi, and J. Sorrell. Reproducibility in learning. InProceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 818–831, 2022

    work page 2022

  40. [40]

    L. Jia, R. Rajaraman, and T. Suel. An efficient distributed algorithm for constructing small dominating sets.Distributed Computing, 15(4):193–205, 2002

    work page 2002

  41. [41]

    Karbasi, G

    A. Karbasi, G. Velegkas, L. Yang, and F. Zhou. Replicability in reinforcement learning.Advances in Neural Information Processing Systems, 36:74702–74735, 2023

    work page 2023

  42. [42]

    F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds.Journal of the ACM, 63(2):1–44, 2016

    work page 2016

  43. [43]

    Kuhn and R

    F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. InProceedings of the twenty-second annual symposium on Principles of distributed computing, pages 25–32, 2003

    work page 2003

  44. [44]

    Kumabe and Y

    S. Kumabe and Y . Yoshida. Average sensitivity of dynamic programming. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1925–1961, 2022

    work page 2022

  45. [45]

    N. Linial. Locality in distributed graph algorithms.SIAM Journal on Computing, 21(1):193–201, 1992

    work page 1992

  46. [46]

    Liu and C

    S. Liu and C. Ye. Replicable uniformity testing.Advances in Neural Information Processing Systems, 37:32039–32075, 2024

    work page 2024

  47. [47]

    Lund and M

    C. Lund and M. Yannakakis. On the hardness of approximating minimization problems.Journal of the ACM, 41(5):960–981, 1994

    work page 1994

  48. [48]

    Moshkovitz

    D. Moshkovitz. Sliding scale conjectures in pcp.ACM SIGACT News, 50(3):25–33, 2019

    work page 2019

  49. [49]

    Moshkovitz and R

    D. Moshkovitz and R. Raz. Two-query PCP with subconstant error.Journal of the ACM, 57(5):1–29, 2008

    work page 2008

  50. [50]

    Murai and Y

    S. Murai and Y . Yoshida. Sensitivity analysis of centralities on unweighted networks. InProceedings of the Web Conference (WWW), pages 1332–1342, 2019

    work page 2019

  51. [51]

    O’Donnell and N

    R. O’Donnell and N. G. Singer. Low-soundness direct-product testers and pcps from kaufman– oppenheim complexes.arXiv preprint arXiv:2511.10514, 2025

    work page arXiv 2025

  52. [52]

    R. Raz. A parallel repetition theorem. InProceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 447–456, 1995

    work page 1995

  53. [53]

    Varma and Y

    N. Varma and Y . Yoshida. Average sensitivity of graph algorithms.SIAM Journal on Computing, 52(4):1039–1081, 2023

    work page 2023

  54. [54]

    Yoshida and S

    Y . Yoshida and S. Ito. Average sensitivity of euclidean k-clustering.Advances in Neural Information Processing Systems, 35:32487–32498, 2022

    work page 2022

  55. [55]

    Yoshida and Z

    Y . Yoshida and Z. Zhang. Low-sensitivity matching via sampling from gibbs distributions. InPro- ceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 120–149, 2026

    work page 2026

  56. [56]

    Yoshida and S

    Y . Yoshida and S. Zhou. Sensitivity analysis of the maximum matching problem. InProceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), pages 58–1, 2021. 112

    work page 2021