AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Laplace mechanism

Definition

Assume Countable Choice. Let $D$ be the finite-support count functions on a nonempty record universe, with neighbors formed by adding or removing one record occurrence. Input a database $D \in D$ , a finite-dimensional query $f : D \to R^{d}$ with finite global $L^{1}$ sensitivity $Δ_{1} f$ , and a parameter $ε > 0$ . If $Δ_{1} f > 0$ , draw $Z$ from the finite product law $Lap (Δ_{1} f / ε)^{\otimes d}$ and release $f (D) + Z$ . If $Δ_{1} f = 0$ , release $f (D)$ deterministically. The output space is $R^{d}$ with its Borel sigma-algebra. Equivalently, for each Borel event $A$ , the output kernel is $K (D, A) = \int 1_{A} (f (D) + z) Lap (Δ_{1} f / ε)^{\otimes d} (d z)$ when $Δ_{1} f > 0$ , and $K (D, A) = 1_{A} (f (D))$ when $Δ_{1} f = 0$ .

Definition references

Finite-dimensional query sensitivity

The scalar Laplace probability law

The finite independent-coordinate Laplace law

The probability-kernel conditions for a randomized mechanism

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Definition 3.3 and Theorem 3.6, printed p. 32.

Vadhan, The Complexity of Differential Privacy, §1.5, PDF pp. 7–8.

Facts & Assumptions

Given: A database $D$ , finite integer $d \geq 1$ , measurable query $f : D \to R^{d}$ , finite $Δ_{1} f \geq 0$ , and $ε > 0$ .

[F1]

Database domain has the power-set sigma-algebra, so every function out of $D$ is measurable.

[A1]

Countable Choice is assumed through the real-valued Laplace law supplier; the finite product adds no stronger choice requirement.

[F2]

Global sensitivity is a finite attained maximum over the add/remove neighboring pairs.

[F3]

Laplace law is a probability measure on $R$ for every scale $b \geq 0$ .

[F4]

Finite products of probability kernels are probability kernels and have the rectangle product law.

[F5]

Borel sigma-algebra on $R^{d}$ is the output measurable structure; translations are homeomorphisms and carry Borel sets to Borel sets.

[F7]

Continuous maps between Borel spaces are measurable; the inverse translation therefore pulls Borel sets back to Borel sets.

[F6]

Probability-kernel conditions require probability-measure sections and measurable evaluation at each output event.

Verification

1.1A1F1F2F3F4F5F7givenconstruct

By [F2], $Δ_{1} f$ is finite and nonnegative, so the zero and positive branches cover every allowed input; if $Δ_{1} f > 0$ , the scale $b = Δ_{1} f / ε$ is positive. By [A1], [F3], and [F4], the noise vector has a probability law $ν = Lap (b)^{\otimes d}$ . For each database $D$ , define the output law as the pushforward of $ν$ under $z \mapsto f (D) + z$ ; the inverse translation is continuous, so [F7] makes the preimage of every Borel set Borel and this is a probability measure.

2.1F1F5F6step 1.1given∎

If $Δ_{1} f = 0$ , assign the point mass at $f (D)$ , which is a probability measure on the Borel output space. For either branch and each Borel event $A$ , the evaluation $D \mapsto K (D, A)$ is measurable because every subset of the database domain is measurable by [F1]. Thus the assignment is a probability kernel as required by [F6].

Depends on

Used by

Add/remove noisy count Example
Thresholding a private noisy count Example
Laplace mechanism privacy Theorem

Dependency tree · two levels

28 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy (standard reference, not scraped)
Salil Vadhan, The Complexity of Differential Privacy, 2017 manuscript (standard reference, not scraped)