{"id":"55765ad3-7d33-4846-9f05-1910f484ce26","arxiv_id":"2607.10952","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Closed-form minimum worst-case error and optimal consistent (ε,δ)-DP mechanisms for counting queries are derived, with conditions for no utility loss under cascaded fixed channels and uncoded M-PSK optimality in high privacy.","lead":"The paper finds a closed-form optimal stochastic mechanism for releasing counting-query answers that is both consistent and (ε,δ)-differentially private, minimizing worst-case error probability. It also shows when a fixed communication channel can be cascaded without utility loss, with uncoded M-PSK over AWGN optimal in high privacy.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript supplies a complete, self-contained solution of the linear program that defines the problem. The propagation argument is original, geometric, and correctly identifies both the optimum value and the entire optimal set. The cascade extension (Theorem 2 and Proposition 1) is carefully conditioned and yields a clean communication-theoretic corollary for M-PSK. The only modeling restriction—worst-case rather than average-case error—is explicitly acknowledged by the authors and by the reader; it does not invalidate the theorems under the utility they optimize. Because the full proofs (including the technical appendices) are present and free of free parameters or circular steps, the reader’s ACCEPT / HIGH-confidence assessment stands. The suggested eigenvalue check is a low-cost sanity verification that would still be worth running, but it is not expected to overturn the claim.","tokens_in":21960,"tokens_out":533,"duration_ms":4592,"concrete_test":"Independently recompute the eigenvalues of the circulant matrix [e^{-ε d_M(i,j)}] for M=5,7,8 (as in Lemma 1 / Appendix A) and verify that the claimed closed-form α_M(ε) indeed normalizes each row of P* to 1 while satisfying the active DP equalities used in the propagation; if any eigenvalue is non-positive for ε>0 the positive-definiteness claim fails and the uniqueness/full-rank statements need re-examination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 1 is internally consistent and rigorously supported by the active-constraint propagation argument (detailed for M=5 and generalized in Appendix B). Feasibility of P* follows directly from the 1-Lipschitz property of the cyclic distance d_M; optimality is established by showing that any attempt to raise all diagonal entries forces the middle row sum(s) above 1 via a cascade of tight (ε,δ)-DP constraints of the form F_i^i = e^ε F_i^{i+1} + δ. The structural claims (shared diagonal/middle-row entries, full-rank conditions, uniqueness only for M=2 or (ε,δ)=(0,0)) follow from the same propagation without additional assumptions. The reader’s weakest assumption (minimax utility) is a transparent modeling choice, not a hidden flaw that undermines the closed-form result under the stated objective. No derivation gap, circularity, or counter-example to the stated claims appears in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies consistent (ε,δ)-differentially private release of M-ary counting queries, where consistency means the output alphabet equals the input message set and utility is the worst-case (minimax) error probability 1−γ(P). Theorem 1 gives the closed-form optimum p*_e=(1−δ)(1−α_M(ε)) attained by the explicit mixture mechanism P*=(1−δ)α_M(ε)[e^{−ε d_M(i,j)}]+δI, and characterises the whole optimal set via propagation of active DP constraints (shared diagonal and middle-row entries, uniqueness only for M=2 or (ε,δ)=(0,0), full-rank conditions). Section V extends the model to a cascade PT with a fixed stochastic medium T, supplies necessary and sufficient conditions for no utility loss (especially in the high-privacy regime), and derives computable upper/lower bounds via convex mixing and spectral perturbation. The theory is illustrated on M-PSK over AWGN, where uncoded transmission is shown to be effectively optimal for small ε.","tokens_in":22161,"tokens_out":687,"duration_ms":5393,"significance":"If correct, the result supplies the first closed-form minimax characterisation of consistent (ε,δ)-DP counting-query release, together with an explicit optimal mechanism and a complete structural description of all optimizers. The cascade analysis and the PSK application give concrete guidance for privacy-preserving communication design. Strengths include a fully rigorous feasibility-plus-propagation proof (no free parameters), explicit full-rank and uniqueness criteria, and transparent modelling choices. The work is therefore a solid contribution to the information-theoretic foundations of differential privacy.","major_comments":[],"minor_comments":[{"comment":"The counter-example after Theorem 1 (M=5, ε=ln1.1, δ=0) is useful but would be clearer if the matrix were displayed with the exact numerical values of α_M(ε) rather than the rounded denominator 5.41.","section":null},{"comment":"Figure 2 caption and axis labels could state more explicitly that the solid curves are exact LP optima while the dashed curves are the upper bounds of Proposition 1; the coincidence of l(T) with the high-SNR asymptotes is mentioned only in the text.","section":null},{"comment":"Notation for the cyclic distance d_M and the auxiliary quantities F_i^i, L_i^{M−i+1} is introduced cleanly, yet a short table of symbols would help readers who jump between the main text and Appendices B–C.","section":null},{"comment":"A few typographical slips remain (e.g., “A WGN” with a space in the abstract, occasional missing commas in long displayed equations). They do not affect readability but should be cleaned in production.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and fits a theory-oriented IT/privacy venue. The modelling choice of minimax utility is transparent and does not undermine the claims under the stated objective. I see no novelty or citation issues that would require editorial intervention."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean, self-contained solution to a natural LP. The headline result is Theorem 1: the minimax error for consistent (ε,δ)-DP release of an M-ary count is exactly (1-δ)(1-α_M(ε)), attained by the explicit cyclic-exponential mixture P* = (1-δ)α_M(ε)[e^{-ε d_M(i,j)}] + δ I. Feasibility follows immediately from the 1-Lipschitz property of cyclic distance; optimality is proved by contradiction via propagation of the active DP constraints that force the middle-row sum(s) above 1. The same propagation then characterizes the whole optimal set (shared diagonal and middle-row entries, uniqueness only for M=2 or (0,0), full-rank conditions). That structural part is the real novelty relative to Ghosh et al., Geng-Viswanath staircase, and truncated Laplace.\n\nThe cascade section is equally careful. Necessary and sufficient conditions for zero utility loss when a fixed stochastic T is present, plus the convex-mixing and spectral-perturbation bounds, are technically sound. The 8-PSK/AWGN numerical example shows uncoded transmission is effectively optimal in the high-privacy regime, which is a concrete communication-theoretic payoff.\n\nThe only modeling limitation worth noting is the exclusive use of worst-case (minimax) error 1-γ(P). That choice drives the entire propagation argument; a Bayesian or average-case utility would change the optimizer. It is transparent, not hidden. No free parameters, no circularity, proofs and appendices are complete, and the citation pattern is appropriate.\n\nThis is for people who work on discrete DP mechanisms or private communication over fixed channels. It deserves a serious referee. I would accept it for peer review and would cite the closed-form and the cascade conditions myself.","headline":"Clean closed-form optimal consistent (ε,δ)-DP counting mechanism plus a full structural characterization of all optimizers; cascade extension is solid and the PSK corollary is useful.","tokens_in":22760,"tokens_out":486,"would_cite":true,"duration_ms":4439,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","94A15","90C05"],"pacs":[],"model":"grok-4.5","headline":"The lowest worst-case error for consistent (ε,δ)-DP counting-query release is exactly (1-δ)(1-α_M(ε)), attained by a simple mixture of identity and a cyclic exponential kernel.","keywords":["differential privacy","counting queries","consistency","worst-case error probability","cyclic exponential kernel","propagation argument","cascaded channels","MPSK AWGN"],"falsifier":"Solve the linear program that maximizes the minimum diagonal entry subject to the (ε,δ)-DP and stochasticity constraints for a concrete triple (M,ε,δ) and check whether the optimum equals (1-δ)(1-α_M(ε)) and whether every optimal matrix shares the diagonal and middle-row entries of the claimed P*.","tokens_in":22826,"feed_emoji":"🔒","tokens_out":812,"duration_ms":6643,"temperature":0.7,"pith_summary":"The paper asks how to release the answer to a counting query so that the release is always a feasible count (consistent), satisfies approximate differential privacy, and keeps the worst-case probability of reporting the wrong count as small as possible. It derives a closed-form expression for that minimal error and an explicit optimal mechanism: a convex combination of the identity map and a cyclic exponential kernel whose entries decay with cyclic distance. Using the active privacy constraints of this mechanism, the authors then characterize every other optimal matrix: they all share the same diagonal and the same middle-row entries, and under mild conditions they are full rank. When part of the communication channel is fixed in advance, the same optimal error is still achievable under explicit conditions on that channel; otherwise convex-mixing and spectral bounds quantify the loss. Applied to M-ary PSK over AWGN, the theory shows that uncoded transmission already meets the ideal optimum in the high-privacy regime.","feed_headline":"Exact min error for private consistent counting queries","feed_subtitle":"Closed form and all optimal mechanisms found; uncoded PSK already optimal when privacy is high","key_machinery":"The canonical optimizer P* together with the propagation of its active differential-privacy equalities. Any attempt to raise all diagonal entries forces neighboring off-diagonal entries upward until a middle-row sum exceeds one, proving optimality and forcing every other optimizer to match P* on the diagonal and middle rows.","core_discovery":"For any M≥2 the minimal worst-case error probability under consistent (ε,δ)-differential privacy is p*_e=(1-δ)(1-α_M(ε)), where α_M(ε) is the normalizing constant of the cyclic exponential kernel. This value is attained by the explicit stochastic matrix P*=(1-δ)α_M(ε)[e^{-ε d_M(i,j)}]+δ I, and every other optimizer shares the diagonal entries and the middle-row structure of P* by propagation of the active privacy constraints.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Exact min error for consistent (ε,δ)-DP counting queries","All optimal private consistent counting mechanisms share structure","Closed-form p*_e=(1-δ)(1-α_M(ε)) for consistent private counts","Cyclic exponential yields every optimal consistent DP count release","Uncoded PSK optimal in high-privacy consistent count release"],"cache_read_input_tokens":128,"weakest_assumption_plain":"Utility is defined solely as the worst-case (minimax) probability of error, that is, one minus the smallest diagonal entry of the mechanism; any other utility measure would change both the optimal value and the mechanism.","fun_headline_variants_meta":{"raw":{"variants":["Exact min error for consistent (ε,δ)-DP counting queries","All optimal private consistent counting mechanisms share structure","Closed-form p*_e=(1-δ)(1-α_M(ε)) for consistent private counts","Cyclic exponential yields every optimal consistent DP count release","Uncoded PSK optimal in high-privacy consistent count release"]},"model":"grok-4.5","effort":"low","cost_usd":0.00561,"raw_usage":{"total_tokens":1499,"prompt_tokens":798,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":56100000,"prompt_tokens_details":{"text_tokens":798,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":625,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":798,"tokens_out":76,"duration_ms":5602,"temperature":1.0,"reasoning_tokens":625,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T08:05:17.310441+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Solve the linear program that maximizes the minimum diagonal entry subject to the (ε,δ)-DP and stochasticity constraints for a concrete triple (M,ε,δ) and check whether the optimum equals (1-δ)(1-α_M(ε)) and whether every optimal matrix shares the diagonal and middle-row entries of the claimed P*.","supporting_citations":[],"review_version":1}