Pith. sign in

REVIEW 3 major objections 4 minor 43 references

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A same-cluster oracle makes correlation clustering exactly recoverable with at most twice its own error count in queries.

desk verdict Valuable COPT parameterization and a clean exact-recovery algorithm, but the lower-bound proof has a false structural claim that invalidates the 'optimal within factor 2' headline as written. read the letter →

arxiv 1908.04976 v1 pith:DA7XPY3L submitted 2019-08-14 cs.DS cs.LG

Barna Saha , Sanjay Subramanian This is my paper · ORCID
classification cs.DScs.LG
keywords correlationclusteringsame-clusterqueriesquerycomplexityoptimalapproximationalgorithmpivotGap-ETHlowerboundcrowdsourcing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that correlation clustering, an NP-hard partitioning problem, becomes substantially easier when an oracle can answer simple same-cluster questions about an optimal solution. The central result is a deterministic pivot algorithm that recovers the exact optimal clustering using at most $2C_{OPT}$ queries, where $C_{OPT}$ is the number of disagreements the optimal clustering makes on the input. A randomized variant reaches a 2-approximation in expectation using at most $C_{OPT}$ expected queries, and the paper proves a conditional lower bound showing that sublinear-in-$C_{OPT}$ queries cannot beat a $1+\alpha$ approximation. Because a good clustering has small $C_{OPT}$, the query budget scales with the unavoidable error in the data rather than with the number of clusters.

What carries the argument

The load-bearing object is a recursive pivot rule. QUERY PIVOT fixes an arbitrary vertex $u$, enumerates every $(+, +, -)$ triangle containing $u$, and for each such triangle queries one or both edges incident to $u$ to learn whether the optimal clustering treats that edge as a mistake; it then forms a cluster from $u$ and its positive neighbors unless a query showed that the optimal clustering makes a mistake on that edge. The bound of $2C_{OPT}$ queries is carried by a charging argument: every query fires only inside a $(+, +, -)$ triangle, and each triangle in which a query is made creates at least one mistake of the algorithm that matches a mistake of the optimal clustering, so total queries are at most twice total mistakes. The randomized version samples each triangle with probability $p$, and its analysis uses a symmetry lemma showing that the probability an edge is queried does not depend on which endpoint is chosen as pivot.

What would settle it

For any complete signed graph, choose an optimal clustering by exhaustive search and let the oracle answer from it; Theorem 3.1 predicts that QUERY PIVOT returns exactly that clustering and asks at most $2C_{OPT}$ questions. A concrete way to test this is to search all signed graphs on, say, up to eight vertices: the first graph on which the algorithm asks more than $2C_{OPT}$ questions, or returns a clustering different from the oracle's, refutes the theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: the deterministic QUERY PIVOT algorithm, given any signed complete graph and an oracle that reports whether the optimal clustering puts two vertices together, outputs exactly that optimal clustering and asks at most $2C_{OPT}$ oracle questions, where $C_{OPT}$ is the number of edges on which the optimal clustering disagrees with the input signs. The randomized variant RANDOM QUERY PIVOT with $p=0.25$ achieves an expected 2-approximation while asking at most $C_{OPT}$ expected questions. The paper further proves, assuming the Gap Exponential-Time Hypothesis, that no polynomial-time algorithm can obtain a $(1+\alpha)$-approximation for an absolute constant $\alpha>0$ while asking $o(C_{OPT})$ questions, so the deterministic query bound is optimal up to a factor of 2.

Load-bearing premise

The oracle must answer correctly and consistently according to a single fixed optimal clustering; if the oracle is noisy or can contradict itself, the exact-recovery guarantee and the $2C_{OPT}$ query bound do not follow.

Editorial extensions

If this is right

  • Exact recovery of the optimal clustering is possible with a query budget that scales with $C_{OPT}$, the unavoidable error, rather than with the number of clusters or vertices; nearly consistent instances are cheap to cluster.
  • The randomized variant gives a 2-approximation in expectation using at most $C_{OPT}$ expected queries, improving on the query-free 2.06-approximation whenever that many questions are allowed.
  • Because the query count is $O(C_{OPT})$, the algorithms remain practical on large instances where LP-based methods with $O(n^3)$ constraints become infeasible, as the experiments on synthetic and real datasets illustrate.
  • Under the Gap Exponential-Time Hypothesis, a $(1+\alpha)$-approximation with $o(C_{OPT})$ queries is impossible in polynomial time, so the deterministic algorithm's $2C_{OPT}$ query bound is within a factor of 2 of the best possible query complexity.
  • A parameterized cluster-editing branching algorithm can be adapted to the same setting and competes with the pivot algorithms in query count, though with different running-time tradeoffs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One direction the paper leaves implicit is a formal noisy-oracle model: the experiments show robustness to crowd-sourced answers, but a theoretical guarantee would require quantifying oracle error and showing that the $2C_{OPT}$ bound degrades gracefully.
  • The mistake-charging argument suggests a budget interpretation: the algorithm spends at most one query per unit of optimal error, essentially using the instance's own noise as currency; extending this charging to weighted graphs or partial observations is a natural next step.
  • If the lower bound is tight, further query reductions must come either from accepting approximation factors above 2 or from richer query types, such as batch queries or answers that reveal more than one edge's status at once.
  • Because each query is charged to a mistake of the optimal clustering, the algorithm could be adapted to an online setting where the estimate of $C_{OPT}$ is refined as mistakes are revealed, stopping early when the budget is exhausted.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies correlation clustering in the same-cluster query model, where an oracle answers whether two vertices belong to the same cluster in an optimal solution. The main theoretical claims are: (i) a deterministic algorithm QUERY PIVOT that recovers an exact optimal clustering using at most 2COPT queries, where COPT is the number of disagreements of the optimal clustering; (ii) a randomized algorithm RANDOM QUERY PIVOT that achieves an expected 2-approximation using at most COPT expected queries; and (iii) a Gap-ETH-based lower bound stating that no polynomial-time algorithm can achieve (1+alpha)-approximation with o(COPT) queries for some constant alpha>0. The paper also reports extensive experiments on synthetic and real-world datasets, including crowd-sourced oracles, comparing against several non-query baselines and a branching algorithm of Bocker et al.

Significance. If correct, the upper-bound results are significant: they give simple, COPT-parameterized query bounds that do not depend on the number of clusters, improving on the k-parameterized bound of Ailon et al., and the exact-recovery bound of 2COPT queries is clean. The experimental section is a strength: it includes real crowd oracles, several real datasets, and a comparison with multiple baselines; the code and data are provided. The lower bound, if correct, would establish near-optimality of the query bound. However, the lower-bound proof as printed contains a false claim about the constructed graph, so the optimality claim is not currently established. The algorithmic upper bounds are interesting in their own right, but the advertised 'optimal query bound within a factor of 2' rests on the unproven lower bound.

major comments (3)
  1. [§5, Appendix 7.2 (Lemma 7.1, proof of Lemma 5.1)] The lower-bound reduction is not valid as written. In the proof of Lemma 5.1, it is claimed that 'for any two vertices that are not +-neighbors the intersection of their +-neighborhoods is of size at most 1', and on that basis Lemma 7.1 is invoked to assert the existence of an optimal solution making mistakes only on + edges. This is false for the constructed graph. For a variable x with c(x)=1, the variable gadget is a cycle of four vertices with + edges (1,2),(2,3),(3,4),(4,1). Vertices 1 and 3 are not +-neighbors, yet N^+(1)={2,4} and N^+(3)={2,4}, so the intersection has size 2; the same holds for 2 and 4. Hence the hypothesis of Lemma 7.1 is not satisfied and the lemma cannot be applied. Consequently, the conclusion that an optimal solution may be assumed to make no mistakes on - edges is unsupported, and the subsequent lower bound COPT >= 10m and the characterization of optimal solutions as deleting all even or all odd + edges in each variable cycle do not follow. Theorem 5.1 and the paper's claim of an 'optimal query bound within a factor of 2' are therefore not proven as written. The authors should repair the construction (e.g., avoid 4-cycles) or provide a direct proof that an optimal solution makes mistakes only on + edges in this graph.
  2. [§4, Algorithm 2] The pseudocode of RANDOM QUERY PIVOT does not match the prose description. In lines 16-22, when the oracle reports a mistake on {pivot,w} at line 20, line 21 sets Mistake[v]<-1 instead of Mistake[w]<-1. Moreover, the comment on line 11 states 'Without loss of generality, suppose that {pivot,v} is a + edge', but the loop over T does not reorder v and w for triangles where {pivot,w} is the + edge and {pivot,v} is the - edge. The pseudocode therefore queries the - edge first in such triangles, contrary to the prose and to the analysis in Lemmas 4.3 and 4.4. As a result, the theorem statements of Section 4 are proven for an algorithm that is not the one implemented in the pseudocode.
  3. [§3, Lemma 3.5] The proof of the query bound of QUERY PIVOT is stated too informally. The claim that 'whenever considering a particular (+,+,-) triangle, if the algorithm makes a query, it makes at most two queries ... and makes at least one mistake that had not been made' is not literally true at the time of the query: if OPT makes exactly one mistake in the triangle and that mistake is on the - edge, then the algorithm queries both + edges and receives 'no mistake' for each; the corresponding output mistake is only made later, when the cluster is formed by including both endpoints of the - edge. A rigorous charging argument, mapping each query to a distinct mistake in the final clustering, is needed. The 2COPT bound may be correct, but the proof as printed does not establish it.
minor comments (4)
  1. [§6, Table 2] The table caption and text use 'sqrt' inconsistently with the dataset name 'sqrtn' defined earlier in Section 6; please unify the terminology.
  2. [§6, Bocker adaptation] The description of the adaptation of Bocker et al.'s branching algorithm to the same-cluster query setting is very brief; a short explanation of how the branching is interleaved with oracle queries would help readers reproduce the experiments.
  3. [Appendix 7.1] The appendix proof of Lemma 4.3 contains confusing notation: the set Yuv is defined, but the case analysis refers to Suv_2u\Yuv_u, and the main-text sketch uses symbols like Suv_u and Tuv_u that are not defined there. The notation should be made consistent throughout.
  4. [References] Reference [21] for the Cora dataset is incomplete (it lists only 'Data.'); please provide the full citation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theory is self-contained given an external oracle, and the lower bound rests on an independent Gap-ETH reduction.

full rationale

The paper's central positive results (Theorems 3.1 and 4.1) are derived from first principles against an oracle that answers consistently with an optimal clustering; no parameter is fitted to the data to force the claimed bounds, and COPT enters only as a parameter of the instance, not as a fitted value. The algorithm QUERY PIVOT queries the oracle only on edges in potential (+, +, -) triangles and makes a mistake on an edge exactly when the oracle reports that the optimal solution makes a mistake, and Lemmas 3.2-3.4 prove that the resulting partition is identical to OPT; the query bound in Lemma 3.5 charges at most two queries per new mistake, so the bound 2COPT is a counting argument rather than an assumption. The randomized algorithm's approximation and query guarantees are proved by a charging argument (Lemmas 4.1-4.4) that bounds expected algorithm mistakes and queries by multiples of OPT's mistakes; the parameter p is a tunable algorithm design choice, not a value fitted to make the proof work. The lower bound is conditional on the independent Gap-ETH hypothesis and follows the external proof strategy of Komusiewicz [18]; the invoked Lemma 7.1 is attributed to that external source rather than to the present authors, so no self-citation chain is load-bearing. Any alleged flaw in the application of Lemma 7.1 to the gadget graph would be a mathematical correctness issue, not a circularity: the lower bound does not assume the target query lower bound as an input. The experimental sections and the comparison to Bocker et al. do not feed fitted constants back into the theorems. Therefore the derivation chain is self-contained and the paper merits a circularity score of 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The main theoretical claims are derived from first principles rather than fitted to data; the only external assumptions are the Gap-ETH hypothesis for the lower bound and the perfect-oracle model. The parameters p and delta are algorithmic design and experimental tuning choices, not free constants that are fit to make the theorems hold.

free parameters (2)
  • p (RANDOM QUERY PIVOT) = 0.25
    Design parameter for the randomized algorithm; the analysis gives a tradeoff max(2,3/(1+2p)) for approximation and max(4p,1)*COPT for expected queries, and p=0.25 is chosen to make both equal 2 and 1. It is not fitted to data.
  • delta (BBC baseline tuning) = selected per dataset by validation
    The Bansal-Blum-Chawla baseline requires a parameter delta; the paper tried several values per dataset and chose the best, which is a data-dependent tuning choice in the experimental comparison only. It does not appear in the theoretical claims.
assumptions (3)
  • domain assumption Gap-ETH (Hypothesis 5.1)
    The lower bound in Section 5 is conditional on the Gap-ETH hypothesis about the hardness of gap 3-SAT. If Gap-ETH is false, the query-complexity lower bound does not follow.
  • domain assumption Oracle consistency with a fixed optimal clustering
    The same-cluster query model assumes an oracle that knows and consistently reveals one optimal clustering. This is the problem setting, but it is strong; the paper's crowd experiments use noisy oracles without formal guarantees.
  • standard math Standard background results in correlation clustering
    The paper relies on known NP-hardness, LP integrality gap, and approximation results (Bansal et al., Ailon et al., Chawla et al.) to frame the problem and compare algorithms. These are external literature results, not derived in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost." pith.science (2026). https://pith.science/paper/DA7XPY3L

@misc{pith2026190804976,
  author       = {Pith},
  title        = {Pith review of: Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DA7XPY3L}},
  note         = {Machine review of arXiv:1908.04976}
}
abstract

Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an oracle with full knowledge of an optimal clustering, and the algorithm can ask the oracle queries of the form, "Does the optimal clustering put vertices $ u $ and $ v $ in the same cluster?" Due to its simplicity, this querying model can easily be implemented in real crowd-sourcing platforms and has attracted a lot of recent work. In this paper, we study the popular correlation clustering problem (Bansal et al., 2002) under this framework. Given a complete graph $G=(V,E)$ with positive and negative edge labels, correlation clustering objective aims to compute a graph clustering that minimizes the total number of disagreements, that is the negative intra-cluster edges and positive inter-cluster edges. Let $ C_{OPT} $ be the number of disagreements made by the optimal clustering. We present algorithms for correlation clustering whose error and query bounds are parameterized by $C_{OPT}$ rather than by the number of clusters. Indeed, a good clustering must have small $C_{OPT}$. Specifically, we present an efficient algorithm that recovers an exact optimal clustering using at most $2C_{OPT} $ queries and an efficient algorithm that outputs a $2$-approximation using at most $C_{OPT} $ queries. In addition, we show under a plausible complexity assumption, there does not exist any polynomial time algorithm that has an approximation ratio better than $1+\alpha$ for an absolute constant $\alpha >0$ with $o(C_{OPT})$ queries. We extensively evaluate our methods on several synthetic and real-world datasets using real crowd-sourced oracles. Moreover, we compare our approach against several known correlation clustering algorithms.

Figures

Figures reproduced from arXiv: 1908.04976 by the authors.

Figure 1
Figure 1. va,4πa(y)−2 va,4πa(y)−3 vc,4πc(y)−3 vc,4πc(y)−2 vy vb,4πb(y)−1 vb,4πb(y)−2 [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [1]

    Ailon, M

    N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. Symposium on the Theory of Computing (STOC), 2005

    work page 2005

  2. [2]

    Approximate correlation clustering using same-cluster queries

    Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal. Approximate correlation clustering using same-cluster queries. In Latin American Symposium on Theoretical Informatics , pages 14–27. Springer, 2018

    work page 2018

  3. [3]

    Approximate clustering with same-cluster queries

    Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate clustering with same-cluster queries. arXiv preprint arXiv:1704.01862, 2017

    arXiv 2017

  4. [4]

    Aggregating inconsistent information: ranking and clustering

    Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):23, 2008

    work page 2008

  5. [5]

    Ashtiani, S

    H. Ashtiani, S. Kushagra, and S. Ben-David. Clustering with same-cluster queries. Advances in Neural Information Processing Systems (NIPS), 2016

    work page 2016

  6. [6]

    M. F. Balcan and A. Blum. Clustering with interactive feedback. International Conference on Algorithmic Learning Theory (ALT), 2008

    work page 2008

  7. [7]

    Bansal, A

    N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Symposium on Foundations of Computer Science (FOCS), 2002

    work page 2002

  8. [8]

    Going weighted: Parameterized algorithms for cluster editing

    Sebastian B¨ocker, Sebastian Briesemeister, Quang Bao Anh Bui, and Anke Truß. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467–5480, 2009

    work page 2009

Show all 43 references
  1. [9]

    Clustering with qualitative informa- tion

    Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative informa- tion. Journal of Computer and System Sciences, 71(3):360–383, 2005

    2005

  2. [10]

    Chawla, K

    S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal lp rounding algorithm for correlation clustering on complete and complete k-partite graphs. Symposium on the Theory of Computing (STOC), pages 219–228, 2015

    2015

  3. [11]

    Febrl: a freely available record linkage system with a graphical user interface

    Peter Christen. Febrl: a freely available record linkage system with a graphical user interface. In Proceedings of the second Australasian workshop on Health data and knowledge management- Volume 80, pages 17–25. Australian Computer Society, Inc., 2008

    2008

  4. [12]

    Correlation clustering in general weighted graphs

    Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172–187, 2006

    2006

  5. [13]

    I. Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 2016

    2016

  6. [14]

    Robust entity resolution using a crowdoracle

    Donatella Firmani, Sainyam Galhotra, Barna Saha, and Divesh Srivastava. Robust entity resolution using a crowdoracle. IEEE Data Eng. Bull., 41(2):91–103, 2018

    2018

  7. [15]

    Semi-supervised algorithms for approxi- mately optimal and accurate clustering

    Buddhima Gamlath, Sangxia Huang, and Ola Svensson. Semi-supervised algorithms for approxi- mately optimal and accurate clustering. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 57:1–57:14, 2018

    2018

  8. [16]

    Giotis and V

    I. Giotis and V . Guruswami. Correlation clustering with a fixed number of clusters. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006

    2006

  9. [17]

    Fault-tolerant entity resolution with the crowd

    Anja Gruenheid, Besmira Nushi, Tim Kraska, Wolfgang Gatterbauer, and Donald Kossmann. Fault-tolerant entity resolution with the crowd. arXiv preprint arXiv:1512.00537, 2015. 14

    2015 arXiv

  10. [18]

    Parameterized Algorithmics for Network Analysis: Clustering and Query- ing

    Christian Komusiewicz. Parameterized Algorithmics for Network Analysis: Clustering and Query- ing. PhD thesis, Elektrotechnik und Informatik der Technischen Universitat Berlin, 2011

    2011

  11. [19]

    Semi-supervised clustering for de-duplication

    Shrinu Kushagra, Shai Ben-David, and Ihab Ilyas. Semi-supervised clustering for de-duplication. arXiv preprint arXiv:1810.04361, 2018

    2018 arXiv

  12. [20]

    Mazumdar and B

    A. Mazumdar and B. Saha. Clustering with noisy queries. Advances in Neural Information Processing Systems (NIPS), 2017

    2017

  13. [21]

    Andrew McCallum. Data

  14. [22]

    Modeling the shape of the scene: A holistic representation of the spatial envelope

    Aude Oliva and Antonio Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. International journal of computer vision, 42(3):145–175, 2001

    2001

  15. [23]

    Entity resolution with crowd errors

    Vasilis Verroios and Hector Garcia-Molina. Entity resolution with crowd errors. In 2015 IEEE 31st International Conference on Data Engineering, pages 219–230. IEEE, 2015

    2015

  16. [24]

    Waldo: An adaptive human interface for crowd entity resolution

    Vasilis Verroios, Hector Garcia-Molina, and Yannis Papakonstantinou. Waldo: An adaptive human interface for crowd entity resolution. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1133–1148. ACM, 2017

    2017

  17. [25]

    Probability with martingales

    David Williams. Probability with martingales. Cambridge university press, 1991

    1991

  18. [26]

    Overview of record linkage and current research directions

    William E Winkler. Overview of record linkage and current research directions. In Bureau of the Census. Citeseer, 2006. 15 Appendix 7.1 Proof of Lemma 4.3 Letsuv = 1 if{u,v} is a− edge and 0 otherwise. Let c∗ uv equal 1 ifOPT makes a mistake on{u,v} and 0 otherwise. LetOPT t b...

    2006

  19. [27]

    Then{u,v} is in exactly one triangle that includes the pivotw, and the algorithm will make a mistake on{u,v} in iteration t regardless of whether uw orvw is queried

    w∈Tuv 1 . Then{u,v} is in exactly one triangle that includes the pivotw, and the algorithm will make a mistake on{u,v} in iteration t regardless of whether uw orvw is queried. Therefore, E[Mt uv|At w] = Pr[Dt uv|At w] = 1

  20. [28]

    Then{u,v} is in exactly one triangle that includes the pivotw, and the algorithm will make a mistake on {u,v} iff the algorithm does not query {u,w}

    w∈Tuv 2u . Then{u,v} is in exactly one triangle that includes the pivotw, and the algorithm will make a mistake on {u,v} iff the algorithm does not query {u,w}. Therefore, E[Mt uv|At w] = 1− Pr[Qt uw|At w]

  21. [29]

    Analogous to case 2: E[Mt uv|At w] = 1− Pr[Qt vw|At w]

    w∈Tuv 2v . Analogous to case 2: E[Mt uv|At w] = 1− Pr[Qt vw|At w]

  22. [30]

    Then recall that{u,v} is a− edge,{u,w} is a + edge, and{v,w} is a− edge

    w∈Yuv u . Then recall that{u,v} is a− edge,{u,w} is a + edge, and{v,w} is a− edge. In this case, whether or not the algorithm queries{u,w}, the algorithm will not make a mistake on{u,v}, soE[Mt uv|At w] = 0

  23. [31]

    Analogous to case 4: E[Mt uv|At w] = 0

    w∈Yuv v . Analogous to case 4: E[Mt uv|At w] = 0

  24. [32]

    Then{u,v} is in exactly one triangle that includes the pivot w, and the algo- rithm will make a mistake on{u,v} iff the algorithm queries{u,w}

    w∈ Suv 2u\Yuv u . Then{u,v} is in exactly one triangle that includes the pivot w, and the algo- rithm will make a mistake on{u,v} iff the algorithm queries{u,w}. Therefore,E[Mt uv|At w] = Pr[Qt uw|At w]

  25. [33]

    Analogous to case 6: E[Mt uv|At w] = Pr[Qt vw|At w]

    w∈Suv 2v\Yuv v . Analogous to case 6: E[Mt uv|At w] = Pr[Qt vw|At w]

  26. [34]

    Then{u,v} is in exactly one triangle that includes the pivotw, and clearlyPr[Mt uv|At w]≤ Pr[Dt uv|At w]

    w∈Ruv. Then{u,v} is in exactly one triangle that includes the pivotw, and clearlyPr[Mt uv|At w]≤ Pr[Dt uv|At w]

  27. [35]

    The expected charge in this case is equal to the sum of the following parts

    w =u. The expected charge in this case is equal to the sum of the following parts. (a) The algorithm makes a mistake on{u,v} iff the algorithm queries{u,v}. The charge for this part is thus Pr[Qt uv|At u]. (b) If the algorithm does not query{u,v}, then∀w∈Tuv 1 , the algorithm ...

  28. [36]

    w = v. Analogous to the previous case: Total (upper bound) is Pr[Qt uv|At v] +|Tuv 1 |(1− Pr[Qt uv|At v]) + 1 2 ∑ w∈T uv 2v 1− Pr[Qt vw|At v] +∑ w∈Suv 2v\Y uvv Pr[Qt vw|At v] Adding the expected charges (or upper bounds thereof) for each of these cases, we obtain: ∑ w∈Vt E[Mt ...

  29. [37]

    Then the algorithm is guaranteed to make a mistake on {u,v} in iteration t, so Pr[Dt uv|At w] = 1

    w ∈ Tuv 1 . Then the algorithm is guaranteed to make a mistake on {u,v} in iteration t, so Pr[Dt uv|At w] = 1

  30. [38]

    Note that the probability that the algorithm makes a mistake on{u,v} in iterationt is then 1− Pr[Qt uw|At w], as noted in the case analysis forE[Mt uv|At w]

    w∈Tuv 2u . Note that the probability that the algorithm makes a mistake on{u,v} in iterationt is then 1− Pr[Qt uw|At w], as noted in the case analysis forE[Mt uv|At w]. Then since Pr[Dt uv|At w] is at least the probability that the algorithm makes a mistake on{u,v} in iteratio...

  31. [39]

    Analogous to case 2: Pr[Dt uv|At w]≥ 1− Pr[Qt vw|At w]

    w∈Tuv 2v . Analogous to case 2: Pr[Dt uv|At w]≥ 1− Pr[Qt vw|At w]

  32. [40]

    Note that the probability that the algorithm makes a mistake on {u,v} in iteration t is equal to Pr[Qt uw|At w], as noted in the case analysis for E[Mt uv|At w]

    w ∈ Suv 2u\Yuv u . Note that the probability that the algorithm makes a mistake on {u,v} in iteration t is equal to Pr[Qt uw|At w], as noted in the case analysis for E[Mt uv|At w]. Then since Pr[Dt uv|At w] is at least the probability that the algorithm makes a mistake on{u,v}...

  33. [41]

    Analogous to case 4: Pr[Dt uv|At w]≥ Pr[Qt vw|At w]

    w∈Suv 2v\Yuv v . Analogous to case 4: Pr[Dt uv|At w]≥ Pr[Qt vw|At w]

  34. [42]

    In this case, we do not simplify Pr[Dt uv|At w] any further

    w∈Ruv. In this case, we do not simplify Pr[Dt uv|At w] any further

  35. [43]

    clause gadget

    w∈{u,v}. Pr[Dt uv|At w] = 1 because the pivot is clustered in iterationt. Hence, ∑ w∈Vt Pr[Dt uv|At w]≥ ∑ w∈T uv 1 1 Case 1 + ∑ w∈T uv 2u Pr[Qtuw|At w] Case 2 + ∑ w∈T uv 2v Pr[Qtvw|At w] Case 3 + ∑ w∈Suv 2u\Y uvu Pr[Qt uw|At w] Case 4 + ∑ w∈Suv 2v\Y uvv Pr[Qt vw|At w] Case 5 +...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.