Lemma 3.3 — rounding error
ProvedLowRandomnessDP.KNorm.Supplement.lemma_3_3differential-privacydiscrete-geometryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and , and let be Algorithm 1 with the smallest minimizing shift. Then
This supplies the common representative radius for the concrete partition at every scale.
Differences from the source:
- encoding: coordinates and the sup-norm bound → coordinates
Fin dand all coordinate absolute errors at most one; reason: these are equivalent for each positive finite dimension
Preamble
import Definitions.Def_LowRandomnessDP_KNorm_Supplement_Rounding set_option autoImplicit false open Classical
Formal statement
namespace LowRandomnessDP.KNorm.Supplement
/-- Lemma 3.3, PDF 11 / printed 9: the coordinate form of the sup-norm bound. -/
theorem lemma_3_3 (d : ℕ) (hd : 0 < d) (x : Vec d) :
∀ i, |R hd x i - x i| ≤ 1 := by sorry
end LowRandomnessDP.KNorm.Supplement
Source
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, STOC 2027 submission #514 (October 2026), Lemma 3.3, PDF p. 11 / printed p. 9; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/514.pdf; SHA-256 1562e70c55d785f992aaa32a161f0b06ac058da62f8f71fb07610037a20bc37b