Permute-and-Flip: Anewmechanismfor differentiallyprivateselection

Infact, bysubstitutingp =1n into Equation (8), weobtain: Proposition 5.For q = ( c,..., c, 0) Rn withc = 2 Δ logn, theexpectederrorE [ E ( MPF, q)] ofpermute-and-flipisatleastΔ2 log ( n).