pith. sign in

arxiv: 2605.17760 · v1 · pith:DIF2LGQBnew · submitted 2026-05-18 · 💻 cs.DS

Tolerant Testing for Unique Games

Yuichi Yoshida This is my paper

Pith reviewed 2026-05-20 01:20 UTC · model grok-4.3

classification 💻 cs.DS
keywords tolerant testingUnique Gamessublinear query complexityproperty testingadjacency list modelbipartiteness testing
0
0 comments X

The pith

Unique Games admit tolerant testers with sublinear query complexity in the adjacency-list model without expansion or clusterability assumptions.

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

The paper presents a tolerant tester for Unique Games that distinguishes instances with optimum violation fraction at most ε from those with optimum at least ρ. It achieves this using a number of adjacency-list queries that scales as the square root of the number of constraints plus a term linear in vertices over square root of constraints, all scaled by inverse powers of ρ. The tester requires no extra assumptions such as graph expansion or clusterability that earlier work needed. A specialized version for the bipartiteness case of Unique Games improves both the tolerance gap and the query bound by using the signed structure of the constraints.

Core claim

We give tolerant testers with sublinear query complexity in the adjacency-list model for Unique Games. Prior tolerant testers required structural assumptions such as expansion or clusterability. For Unique Games, the tester distinguishes instances whose optimum fraction of violated constraints is at most ε from those whose optimum is at least ρ, for 0<ε<ρ<1, assuming ε log n ≲ ρ^4. On instances with n vertices and m constraints, it uses Õ(√m ρ^{-13/2} + n ρ^{-2}/√m) queries. We also give a specialized tester for bipartiteness with improved guarantees using λ = ρ/(1 + log(1/ρ)) and Õ(√m/λ² + n/(√m λ)) queries under ε log n ≲ λ².

What carries the argument

The sublinear-query tolerant tester that samples vertices and constraints from the adjacency-list representation to estimate the minimum violation fraction and separate the low-violation regime from the high-violation regime.

If this is right

  • Tolerant testing now applies to arbitrary Unique Games instances rather than only those satisfying expansion or clusterability.
  • The query complexity stays sublinear in the total input size for regimes where m is not too small compared to n and the tolerance gap satisfies the given relation.
  • The bipartiteness specialization yields strictly better tolerance and query bounds whenever the Unique Game reduces to checking bipartiteness via edge deletions.

Where Pith is reading between the lines

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

  • The sampling approach may extend directly to other constraint satisfaction problems whose value can be estimated by local queries.
  • Combining the tester with existing approximation algorithms could yield end-to-end sublinear-time pipelines for large sparse Unique Games instances.
  • Closing the polynomial gap between ε and ρ in the assumption would widen the practical range of tolerance gaps the method can handle.

Load-bearing premise

The relation ε log n ≲ ρ^4 that allows the tester to separate the ε-satisfiable case from the ρ-unsatisfiable case.

What would settle it

Run the tester on a concrete Unique Games instance with known optimum violation exactly between ε and ρ; the tester should output the wrong answer with noticeable probability when the query budget is respected and ε log n is only slightly larger than ρ^4.

read the original abstract

We give tolerant testers with sublinear query complexity in the adjacency-list model for Unique Games. Prior tolerant testers required structural assumptions such as expansion or clusterability. For Unique Games, the tester distinguishes instances whose optimum fraction of violated constraints is at most $\varepsilon$ from those whose optimum is at least $\rho$, for $0<\varepsilon<\rho<1$, assuming $\varepsilon\log n\lesssim\rho^4$. On instances with $n$ vertices and $m$ constraints, it uses $\widetilde O(\sqrt m\,\rho^{-13/2}+n\rho^{-2}/\sqrt m)$ queries. We also give a specialized tester for bipartiteness, the $Q=2$ transposition case of Unique Games. Exploiting its signed structure, the tester achieves substantially better tolerance and query-complexity guarantees than the generic Unique Games tester. Writing $\lambda=\rho/(1+\log(1/\rho))$, the bipartiteness tester distinguishes graphs that can be made bipartite by deleting at most an $\varepsilon$ fraction of edges from graphs in which every bipartition has at least a $\rho$ fraction of edges with both endpoints on the same side, assuming $\varepsilon\log n\lesssim\lambda^2$, using $\widetilde O(\sqrt m/\lambda^2+n/(\sqrt m\,\lambda))$ queries.

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

0 major / 2 minor

Summary. The paper claims to give the first sublinear-query tolerant testers for Unique Games in the adjacency-list model, distinguishing instances with optimum violation fraction at most ε from those with optimum at least ρ (for 0<ε<ρ<1) under the assumption ε log n ≲ ρ^4. The query bound is Õ(√m ρ^{-13/2} + n ρ^{-2}/√m) on n-vertex, m-constraint instances. A specialized tester for the Q=2 (bipartiteness) case exploits signed structure to obtain improved tolerance and query complexity: with λ=ρ/(1+log(1/ρ)), it distinguishes ε-close-to-bipartite graphs from those with ρ-fraction monochromatic edges under ε log n ≲ λ^2 using Õ(√m/λ^2 + n/(√m λ)) queries.

Significance. If the stated bounds and assumption suffice for the analysis, the result is significant: it removes the need for expansion or clusterability assumptions that prior tolerant testers required, while giving explicit, sublinear query complexity in the natural adjacency-list model. The explicit parameter relation and the improvement for the bipartiteness special case are concrete strengths. The work advances property testing for CSPs by handling general Unique Games instances under a mild, explicitly stated precondition.

minor comments (2)
  1. [Abstract] Abstract: the notation Õ is used without definition; a brief parenthetical expansion (e.g., hiding polylog factors) would improve readability for readers outside the immediate subfield.
  2. [Abstract] The assumption ε log n ≲ ρ^4 is stated as a precondition; a short remark on whether it is necessary or merely sufficient for the current analysis would help contextualize the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The referee's summary correctly captures the main results on sublinear-query tolerant testing for Unique Games and the improved bipartiteness tester. We are pleased that the contribution is viewed as significant for removing structural assumptions in the adjacency-list model.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents an explicit algorithmic construction for a tolerant tester for Unique Games in the adjacency-list model, with query complexity derived from standard sampling techniques under the explicitly stated precondition ε log n ≲ ρ^4. No equations, parameters, or central claims reduce by construction to fitted inputs, self-definitions, or self-citation chains; the assumption is presented as a precondition rather than derived, and the bipartiteness specialization exploits signed structure without circular reduction. The derivation is self-contained against external benchmarks of query complexity analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard mathematical assumptions from graph theory and algorithm analysis plus the domain-specific tolerance condition ε log n ≲ ρ^4.

axioms (1)
  • standard math Standard assumptions of graph theory and randomized algorithm analysis hold.
    The query complexity analysis and distinction rely on typical probabilistic method and graph sampling arguments.

pith-pipeline@v0.9.0 · 5751 in / 1092 out tokens · 46602 ms · 2026-05-20T01:20:57.460567+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Random sampling and approximation of MAX-CSPs.Journal of Computer and System Sciences, 67(2):212–243, 2003

    Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, and Marek Karpinski. Random sampling and approximation of MAX-CSPs.Journal of Computer and System Sciences, 67(2):212–243, 2003

    work page 2003

  2. [2]

    Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy. InProceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 21–28, 2008

    work page 2008

  3. [3]

    Springer Singapore, 2022

    Arnab Bhattacharyya and Yuichi Yoshida.Property Testing: Problems and Techniques. Springer Singapore, 2022

    work page 2022

  4. [4]

    Testing graph clusterability: Algorithms and lower bounds

    Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. InProceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 497–508, 2018. 43

    work page 2018

  5. [5]

    Testing cluster structure of graphs

    Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 723–732, 2015

    work page 2015

  6. [6]

    Testing expansion in bounded-degree graphs.Combina- torics, Probability and Computing, 19(5–6):693–709, 2010

    Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs.Combina- torics, Probability and Computing, 19(5–6):693–709, 2010

    work page 2010

  7. [7]

    On sampling edges almost uniformly

    Talya Eden and Will Rosenbaum. On sampling edges almost uniformly. InProceedings of the 1st Symposium on Simplicity in Algorithms (SOSA), volume 61 ofOpen Access Series in Informatics (OASIcs), pages 7:1–7:9, 2018

    work page 2018

  8. [8]

    Tolerant bipartiteness testing in dense graphs

    Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen. Tolerant bipartiteness testing in dense graphs. InProceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:19, 2022

    work page 2022

  9. [9]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM, 42(6):1115– 1145, 1995

    work page 1995

  10. [10]

    Cambridge University Press, 2017

    Oded Goldreich.Introduction to Property Testing. Cambridge University Press, 2017

    work page 2017

  11. [11]

    A sublinear bipartiteness tester for bounded degree graphs

    Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica, 19(3):335–373, 1999

    work page 1999

  12. [12]

    Approximating unique games

    Anupam Gupta and Kunal Talwar. Approximating unique games. InProceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 99–106, 2006

    work page 2006

  13. [13]

    A sublinear time tester for Max-Cut on clusterable graphs

    Agastya Vibhuti Jha and Akash Kumar. A sublinear time tester for Max-Cut on clusterable graphs. InProceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), volume 297 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 91:1–91:17, 2024

    work page 2024

  14. [14]

    On the notion of recurrence in discrete stochastic processes.Bulletin of the American Mathematical Society, 53(10):1002–1010, 1947

    Mark Kac. On the notion of recurrence in discrete stochastic processes.Bulletin of the American Mathematical Society, 53(10):1002–1010, 1947

    work page 1947

  15. [15]

    Seshadhri

    Satyen Kale and C. Seshadhri. An expansion tester for bounded degree graphs.SIAM Journal on Computing, 40(3):709–720, 2011

    work page 2011

  16. [16]

    Tight bounds for testing bipartiteness in general graphs.SIAM Journal on Computing, 33(6):1441–1483, 2004

    Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs.SIAM Journal on Computing, 33(6):1441–1483, 2004

    work page 2004

  17. [17]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. InProceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 767–775, 2002

    work page 2002

  18. [18]

    Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing, 37(1):319–357, 2007

    Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing, 37(1):319–357, 2007

    work page 2007

  19. [19]

    Spectral algorithms for unique games.Computational Complexity, 20(2):177– 206, 2011

    Alexandra Kolla. Spectral algorithms for unique games.Computational Complexity, 20(2):177– 206, 2011. 44

    work page 2011

  20. [20]

    Frustration index and Cheeger inequalities for discrete and continuous magnetic laplacians.Calculus of Variations and Partial Differential Equations, 54:4165–4196, 2015

    Carsten Lange, Shiping Liu, Norbert Peyerimhoff, and Olaf Post. Frustration index and Cheeger inequalities for discrete and continuous magnetic laplacians.Calculus of Variations and Partial Differential Equations, 54:4165–4196, 2015

    work page 2015

  21. [21]

    Bidirectional PageRank estimation: From average-case to worst-case

    Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional PageRank estimation: From average-case to worst-case. InProceedings of the 12th International Workshop on Algorithms and Models for the Web Graph (WAW), volume 9479 ofLecture Notes in Computer Science, pages 164–176, 2015

    work page 2015

  22. [22]

    Random walks in a convex body and an improved volume algorithm.Random Structures & Algorithms, 4(4):359–412, 1993

    L´ aszl´ o Lov´ asz and Mikl´ os Simonovits. Random walks in a convex body and an improved volume algorithm.Random Structures & Algorithms, 4(4):359–412, 1993

    work page 1993

  23. [23]

    Yet another algorithm for dense Max Cut: Go greedy

    Claire Mathieu and Warren Schudy. Yet another algorithm for dense Max Cut: Go greedy. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 176–182, 2008

    work page 2008

  24. [24]

    Tolerant property testing and distance approximation.Journal of Computer and System Sciences, 72(6):1012–1042, 2006

    Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation.Journal of Computer and System Sciences, 72(6):1012–1042, 2006

    work page 2006

  25. [25]

    Sublinear-time algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on expanders

    Pan Peng and Yuichi Yoshida. Sublinear-time algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on expanders. InProceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4936–4965, 2023

    work page 2023

  26. [26]

    Approximation algorithms for unique games.Theory of Computing, 4(5):111–128, 2008

    Luca Trevisan. Approximation algorithms for unique games.Theory of Computing, 4(5):111–128, 2008

    work page 2008

  27. [27]

    Max Cut and the smallest eigenvalue.SIAM Journal on Computing, 41(6):1769– 1786, 2012

    Luca Trevisan. Max Cut and the smallest eigenvalue.SIAM Journal on Computing, 41(6):1769– 1786, 2012. A Proofs for the Preliminaries A.1 Heat-kernel L1-gradient averaging This proof justifies the L1-gradient averaging lemma used in the trace-chain sweep arguments. The point is to get the gradient bound from entropy decay in a finite lazy reversible chain,...

    work page 2012