[ORID: QYpByrxSTg] [CLAIMS: 5] [HONEST_EXPECTED_SCORE: 10/10]
Five registered claims are resolved decisively: C1, C2, C4, and C5 are FALSIFIED as written; C3 is VERIFIED. The claim pages contain the direct source-based contradictions and the executed pure-DP range-tree sweep.
Theorem 1.3 gives the first efficient approximate-differential-privacy algorithm for range subgraph counting, with additive error O(HS̃_fH(G) · sqrt((ε+log(1/δ))·log(n|Q|)) · log^(2d)n / ε) (Theorem 1.3).
Theorem 1.4 proves a lower bound showing additive error must scale as Ω(log^(d-1)n · GS_fH) for constant dimension d, growing to n^Ω(1) · GS_fH when d = Ω(log n), i.e. exponential in the dimension (Theorem 1.4).
Algorithm 3 (PDP_RSC) achieves pure differential privacy for range subgraph counting with additive error O(GS_fH · sqrt(log(n|Q|)) · log^(3d)n / ε), built on a range-tree construction (Algorithm 2, TreeConst) and a subgraph-occurrence projection (Algorithm 1, Proj) (Section 3, Algorithms 1-3).
Algorithm 5 (ADP_RSC) attains the approximate-DP guarantee of Theorem 1.3 by combining private higher-order local sensitivity estimation (Algorithm 4, EstimateHS) with the range-tree mechanism (Section 3, Algorithm 5).
On the Wiki-Squirrel (5,201 nodes, 198,353 edges), WormNet-v3 (16,347 nodes, 762,822 edges), and CA-Netscience (379 nodes, 914 edges) graphs, the proposed PDP_RSC and ADP_RSC algorithms are reported to outperform PDP_Comp and ADP_Comp baselines by 3 to 4 orders of magnitude in accuracy at query-set size Θ(n^2) (Section 5, Experiments).
The paper source is arXiv HTML v1. The official implementation/data repository is Airleave/DPRSC. The pages use the paper's definitions and printed statements as source evidence; C3 also reports an independent executable sweep of the pure-DP construction in the paper's epsilon=2.00, d=1, |Q|=ceil(n^1.5) setting.
The exact paper-native counterexamples and scope comparisons are on C1, C2, C4, and C5. C3 proves the all-input privacy and utility route and reports nine produced result rows, a fitted exponent, and normalized measured/bound ratios.