{"id":"cc1557f5-edc7-419f-93cd-ec914c2c539c","arxiv_id":"2506.20234","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A sparse-vector randomized response can be published with O(εd) communication and O(d) computation by randomly partitioning the vector and applying Poisson Private Representation chunk-wise, while preserving the output distribution.","lead":"This paper proposes a compressed version of randomized response for publishing sparse high-dimensional vectors, using shared randomness and random chunking to cut communication from Ω(n×N) to O(εd). A generalist might read it because it claims privacy that becomes cheaper as the privacy budget shrinks, a counterintuitive and practically attractive property.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Data-dependent chunk count m = βεd leaks sparsity through transcript length; all-zero vs one-hot inputs have disjoint output supports, so Theorem 5's 2αε-metric DP guarantee fails.","rationale":"The reader and I converge on the same load-bearing flaw: Theorem 5's parallel-composition argument requires a fixed partition of coordinates, but §4 fixes m = βεd, a function of the private sparsity d. Since the output is a tuple of m PPR messages, the tuple length is observable and varies with d. The all-zero versus one-hot pair is a direct counterexample: at Hamming distance 1, one input has m = 0 and the other has m > 0, so the output supports are disjoint and the metric-DP inequality fails for the set containing only the empty transcript. This is not a matter of outside-current-consensus disagreement but of the stated definition failing on a concrete pair. It is not repaired by the claim that the decoded vector has the same distribution as randomized response, because the transcript itself is the mechanism output and its length is public; decoding is post-processing. The Hoeffding citation in Theorem 1 has the inequality reversed, but the application in Theorem 7 uses the correct direction, so I do not treat that as the primary blocker. The experimental evaluation is useful but cannot validate a privacy theorem that is false as written. Therefore the central claim is unsupported and the rejection verdict stands.","tokens_in":13774,"tokens_out":10479,"duration_ms":109781,"concrete_test":"Re-run the privacy check on the two inputs v0 = 0^n and v1 = e_i with ε = 1, α = 2, β = 2, giving m(v0) = 0 and m(v1) = 2. Enumerate or symbolically compute the output supports; they are disjoint by tuple length, so P[M(v0) = ∅] = 1 and P[M(v1) = ∅] = 0. Evaluating Definition 1 at S = {∅} yields 1 ≤ e^{4} · 0, which is false. If the authors instead intend m to be public and independent of d, the experiment should be repeated with a fixed m, and the Theorem 6 communication bound must be recomputed, since it currently relies on m = βεd.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 takes m as an input, and §4 sets m = βεd, where d is the private number of non-zero entries. The output is a tuple of m PPR messages, so the transcript length is an observable function of d. Consider binary vectors under Hamming distance: v0 = 0^n and v1 = e_i, with H(v0, v1) = 1. For v0, the analysis gives m = 0 and output ∅ with probability 1. For v1, m = βεd > 0 (e.g., β = 2, ε = 1 gives m = 2), so the output is a non-empty tuple and never equals ∅. Let S = {∅}. Then P[M(v0) ∈ S] = 1 but P[M(v1) ∈ S] = 0, so the required inequality 1 ≤ e^{2αε·1} · 0 fails for every finite α, ε. The parallel-composition argument in Theorem 5 is valid only for a fixed m independent of the data; it cannot absorb a data-dependent output length. Therefore the stated 2αε-metric DP guarantee is false for Algorithm 1 as parameterized in §4. A secondary inconsistency is that Theorem 1 states the hypergeometric/binomial inequality reversed relative to Hoeffding's Theorem 4, although the application in Theorem 7 appears to use the correct direction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a protocol for releasing randomized-response-obfuscated sparse vectors under metric differential privacy, with communication and computation costs claimed to depend on the sparsity d rather than the vector length n. The protocol (Algorithm 1) randomly permutes the coordinates, partitions them into m chunks, and compresses each chunk's randomized response using the Poisson Private Representation (PPR) of Liu et al. [24]; Algorithm 2 decodes any coordinate, and Algorithm 3 computes the likelihood ratio using only the non-reference coordinates. Section 4 sets m = βεd and claims that the mechanism satisfies 2αε-metric differential privacy (Theorem 5), has O(εd) expected communication (Theorem 6), and O(d) expected computation (Theorem 7). Section 5 describes applications to social-network adjacency lists, recommendation ratings, and SNP data, and Section 6 reports experiments on MovieLens, 1000 Genomes, Wikipedia, and Google+ data.","tokens_in":14049,"tokens_out":7612,"duration_ms":81954,"significance":"If valid, the main result would be an important advance: an exact, distribution-preserving randomized-response publication scheme whose communication scales as O(εd), potentially beating the non-private Ω(d log n) cost for sparse vectors, with experiments suggesting large practical gains. The paper deserves credit for a concrete protocol design, an anonymous reproducible implementation, and a fairly extensive experimental evaluation across several domains. However, the headline privacy theorem is false as stated because the transcript length is data-dependent, so the claimed privacy–communication trade-off is not established. The computational complexity analysis also relies on a misstated version of Hoeffding's inequality. The core idea of random chunking to make PPR tractable may be salvageable in a revised form, but not with the current privacy guarantee.","major_comments":[{"comment":"The privacy proof treats m as a fixed parameter, but §4 sets m = βεd, where d is the private Hamming distance to the reference. The output of Algorithm 1 is a tuple of length m, so the transcript length is an observable deterministic function of d. Let v0 be the all-zero vector and v1 a vector with a single 1; then H(v0, v1) = 1. For v0, m = 0 and the output is the empty tuple with probability 1; for v1, m = βε > 0 and the output is a non-empty tuple, so the two output supports are disjoint. Taking S = {∅} gives P[M(v0) ∈ S] = 1 and P[M(v1) ∈ S] = 0, so the required 2αε-metric DP inequality fails for every finite α and ε. Parallel composition can only be applied to a fixed, data-independent set of chunks, and cannot absorb a data-dependent output length. This invalidates the central privacy claim and, with it, the claimed privacy–communication trade-off.","section":"§4, Theorem 5 and Algorithm 1"},{"comment":"The displayed inequality is reversed relative to Hoeffding's Theorem 4. For a continuous convex function f, with Y hypergeometric(N, K, n) and X binomial(n, K/N), the correct Hoeffding bound is E[f(Y)] ≤ E[f(X)], since the hypergeometric is less spread out than the binomial with the same mean. The paper states E[f(X)] ≤ E[f(Y)]. Moreover, the proof of Theorem 7 invokes Theorem 1 to upper-bound E[C_i(d_i)] by the expectation under a binomial Y, which uses the correct direction. The theorem statement should be corrected; as written it is false.","section":"§2.1, Theorem 1"}],"minor_comments":[{"comment":"The displayed bound appears to be missing a division sign: it reads \"log2 3.56 min{(α−1)/2,1}\" where the discussion immediately before it has \"log2(3.56/min{(α−1)/2,1})\"; the same typo appears in the proof of Theorem 6.","section":"§2.4, Theorem 4"},{"comment":"The sentence \"our precision is 104 better than any previous works\" presumably means 10^4; please use math mode or superscript formatting.","section":"§1.1"},{"comment":"The statement that \"all 1,000 executions maintain a manageable execution time\" is informal; reporting a maximum and a high percentile would make the variance claim interpretable.","section":"§6.1"},{"comment":"The input is declared as a list of distributions (Q1, ..., Qn), but the pseudocode uses only Q_i for the queried index; clarify whether the list contains per-coordinate or per-chunk candidate distributions.","section":"Algorithm 2"}],"recommendation":"reject","confidential_remarks":"This is a clear reject for me: the main theorem is false because the transcript length is data-dependent, and the issue is not fixable by a local edit. Making m public, for example by using an upper bound on d, would change the claimed O(εd) communication to O(εD) and is a different result. I would be open to reconsidering a revised version that either fixes this privacy hole or states a valid but weaker guarantee."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is genuinely new and worth thinking about: randomly partition a sparse vector into m chunks so each chunk has O(1) non-zeros in expectation, then run PPR per chunk and compute the likelihood ratio only on the d coordinates that differ from a public reference. Conditional on a fixed m, the communication and computation analyses are coherent, and the experiments on MovieLens, 1000 Genomes, and the Wikipedia graph are reasonable. The random partitioning trick and the O(d) ratio computation are solid contributions that go beyond the contiguous chunking in [24].\n\nThe problem is the privacy accounting. Section 4 sets m = βεd, where d is the private number of non-zero entries. Algorithm 1 outputs a tuple of m PPR messages, so the output length itself is a deterministic function of d. The proof of Theorem 5 applies parallel composition to a fixed set of m chunks and completely ignores that m is data-dependent. The stress-test example is decisive: take v0 = 0ⁿ and v1 = e_i at Hamming distance 1. For v0, m=0 and the output is the empty tuple with probability 1. For v1, m>0 and the output is never empty. Let S={∅}; then Pr[M(v0)∈S]=1 while Pr[M(v1)∈S]=0, violating the metric DP inequality for any finite α, ε. So the 2αε-metric DP guarantee is false as written.\n\nThere's also a smaller issue in Theorem 1: the direction of the binomial-vs-hypergeometric inequality is reversed relative to Hoeffding's Theorem 4. The application in Theorem 7 uses the correct direction (hypergeometric is less variable), so this looks like a typo, not a load-bearing error.\n\nThe consequence is that the headline claims — communication O(εd) and computation O(d) independent of n — rest on an algorithm that does not actually meet its privacy guarantee. If m were fixed to a public upper bound on d, the privacy proof could be repaired, but then communication would depend on d_max, not d, and the main practical advantage would weaken. The paper does not offer that repair.\n\nI still think this is a serious paper in the sense that the authors are thinking clearly about a real problem and the idea is worth exploring. The flaw is a specific, fixable-in-principle oversight rather than incoherence. But as it stands, the central theorem is false, so I would not cite it as a privacy-preserving mechanism. For a reading group on differential privacy, it's a great example of data-dependent transcript length breaking composition arguments.\n\nRecommendation: send it to peer review — a good referee will catch this and may be able to suggest the fix — but be prepared to reject unless the privacy analysis is reworked.","headline":"Nice compression idea, but the privacy proof is broken: m=βεd leaks the sparsity d through the transcript length, so Theorem 5's 2αε-metric DP guarantee is false as stated.","tokens_in":14582,"tokens_out":3244,"would_cite":false,"duration_ms":37184,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that randomized response on sparse vectors can be compressed to O(εd) communication and O(d) computation, preserving the exact output distribution under 2αε-metric differential privacy.","keywords":["Differential privacy","Metric differential privacy","Randomized response","Sparse vectors","Poisson private representation","Communication cost","Local differential privacy","Graph privacy"],"falsifier":"Run Algorithm 1 on the all-zero vector and on the vector with a single 1 at the same ε, α, β; the first transcript is empty (m = 0) and the second has m = βε chunk indices, so the output supports are disjoint. For the second input, the outcome corresponding to its own transcript has positive probability, while under the first input that outcome has probability 0, giving an unbounded ratio P[M(x) ∈ S] / P[M(x′) ∈ S] for two Hamming-distance-1 inputs and refuting the claimed 2αε-metric differential privacy.","tokens_in":13578,"feed_emoji":"🔒","tokens_out":7477,"duration_ms":71273,"temperature":0.7,"pith_summary":"This paper tries to establish that publishing a high-dimensional sparse vector under metric differential privacy need not be expensive: a user can send a compressed randomized response whose expected length is O(εd) bits, where ε is the privacy budget and d is the number of non-trivial entries, instead of the Ω(n) bits of a naive randomized response. The claimed compression is exact in distribution: the server's reconstructed vector is identically distributed to the randomized response of the original vector, so downstream estimators designed for randomized response remain valid. If the claim holds, private data collection for social-network adjacency, user-item ratings, and SNP data becomes cheaper than even the non-private sparse representation, and smaller ε—stronger privacy—makes communication cheaper rather than more expensive. The paper supports the claim with a theoretical analysis (Theorems 5–7) and experiments on three application datasets.","feed_headline":"Sparse-vector privacy now costs O(εd) bits to send","feed_subtitle":"A compressed randomized response keeps the exact output distribution while beating non-private sparse upload costs.","key_machinery":"Poisson Private Representation (PPR): a method from [24] that simulates any differentially private mechanism by having the user and server share a counter-based PRNG and a candidate distribution Q; the user transmits only the index K of the draw from Q that is accepted as the mechanism's output, so the server's reconstruction has the same distribution as the original mechanism. The paper's contribution is wrapping PPR in a random partitioning: a public random permutation φ splits the vector into m = βεd chunks, keeping the expected number of non-trivial elements per chunk constant, and the likelihood ratio dP/dQ is evaluated by Algorithm 3, which multiplies $e^{\\varepsilon}$ or $e^{-\\varepsilon}$ only over the coordinates where the private vector differs from the reference. This machinery turns PPR's per-chunk cost into something that scales with d rather than n, making both communication and computation linear in d.","core_discovery":"The central discovery is that Poisson Private Representation (PPR), which normally has communication cost that grows with the vector's length n, can be made to depend only on the sparsity d if the vector is first randomly permuted and split into m = βεd chunks, each carrying a constant expected number of non-trivial entries. The encoding algorithm, Algorithm 1, applies PPR independently to each chunk with candidate distribution equal to randomized response applied to the reference vector; Algorithm 2 decodes any coordinate in constant time using counter-based PRNGs; and Algorithm 3 computes the required likelihood ratio dP/dQ using only the d′ coordinates where the input differs from the reference, avoiding generation of the full vector. The paper proves that the output is identically distributed to randomized response, that the combined mechanism satisfies 2αε-metric differential privacy by parallel composition (Theorem 5), that expected communication is O(εd) (Theorem 6), and that expected computation is O(d) (Theorem 7), all independent of n.","pith_inferences":["The same random-chunking wrapper could plausibly compress other local mechanisms beyond randomized response: any mechanism whose likelihood ratio against a public reference distribution is nonzero only on a sparse set of coordinates can in principle reuse Algorithm 3's coordinate-local ratio computation.","Because the compressed output is identical in distribution to randomized response, the algorithm can be dropped into existing downstream pipelines—subgraph counting, synthetic graph generation, common-neighbor estimation—without re-deriving their error or unbiasedness guarantees.","The cost reversal (smaller ε lowers communication) suggests a practical operating point: systems could automatically tighten privacy when bandwidth is scarce, a trade-off direction that previous communication-constrained schemes did not offer."],"forward_implications":["In a social network, each user can publish their adjacency list under edge-local differential privacy with communication proportional to their degree d rather than the number of nodes n, enabling the two-step triangle and cycle counting frameworks to operate at a fraction of the previous communication cost.","Recommendation-system interaction matrices can be published with upload cost proportional to the number of items a user has rated, making local private collection feasible at the scale of millions of items.","For genomic SNP data, a user sends communication proportional to the number of locations where they differ from the most frequent variant, with a reference vector built from population frequencies.","Because the released distribution is exactly randomized response, any estimator, unbiasedness property, or post-processing that works on randomized response works unchanged on the compressed output.","As ε decreases, m = βεd decreases too, so stronger privacy reduces communication cost — the opposite of the behavior of prior communication-constrained randomized response schemes."],"supporting_citations":[{"why":"Supplies the PPR machinery (Theorems 3 and 4) that the algorithm wraps, giving distribution preservation and the communication bound per chunk.","marker":"[24]"},{"why":"Provides counter-based PRNGs used for constant-time decoding of any coordinate from the transmitted index.","marker":"[29]"},{"why":"Hoeffding's convex-order result lets the computation bound in Theorem 7 replace the hypergeometric chunk size with a binomial one.","marker":"[13]"},{"why":"Defines metric differential privacy, the privacy notion the algorithm is analyzed under.","marker":"[1]"},{"why":"Defines randomized response, the mechanism whose output distribution the compressed protocol must reproduce exactly.","marker":"[31]"},{"why":"The two-step subgraph counting framework whose communication cost motivates the problem and provides the triangle-counting experiment.","marker":"[16]"},{"why":"Invoked in Theorem 5 as the parallel composition principle that yields the 2αε-metric DP guarantee across chunks.","marker":"[26, 25]"}],"fun_headline_variants":["Sparse vectors now get O(εd) privacy cost, not O(n)","Exact private output with communication O(εd) bits","Privacy scales with nonzero entries, not vector size","Randomized response without the upload burden: O(εd)","Sparse data privacy: communication drops to O(εd)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands or falls on the assumption that choosing the chunk count m = βεd, which reveals the private sparsity d, does not itself leak anything — so a user with d = 0 and a user with d = 1 may be compared.","fun_headline_variants_meta":{"raw":{"variants":["Sparse vectors now get O(εd) privacy cost, not O(n)","Exact private output with communication O(εd) bits","Privacy scales with nonzero entries, not vector size","Randomized response without the upload burden: O(εd)","Sparse data privacy: communication drops to O(εd)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000318,"raw_usage":{"total_tokens":1787,"prompt_tokens":929,"completion_tokens":858,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":771}},"tokens_in":545,"tokens_out":858,"duration_ms":8631,"temperature":1.0,"reasoning_tokens":771,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:23:03.911758+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on the all-zero vector and on the vector with a single 1 at the same ε, α, β; the first transcript is empty (m = 0) and the second has m = βε chunk indices, so the output supports are disjoint. For the second input, the outcome corresponding to its own transcript has positive probability, while under the first input that outcome has probability 0, giving an unbounded ratio P[M(x) ∈ S] / P[M(x′) ∈ S] for two Hamming-distance-1 inputs and refuting the claimed 2αε-metric differential privacy.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the PPR machinery (Theorems 3 and 4) that the algorithm wraps, giving distribution preservation and the communication bound per chunk."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides counter-based PRNGs used for constant-time decoding of any coordinate from the transmitted index."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Hoeffding's convex-order result lets the computation bound in Theorem 7 replace the hypergeometric chunk size with a binomial one."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines metric differential privacy, the privacy notion the algorithm is analyzed under."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines randomized response, the mechanism whose output distribution the compressed protocol must reproduce exactly."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The two-step subgraph counting framework whose communication cost motivates the problem and provides the triangle-counting experiment."}],"review_version":2}