WebeginbyMPF, which willreference Lemma 1.PFcanbe Pr[ MPF(q) = rr

Step (b) cancels commonterms (thosethatdonotcontain1 pr or1 ps). Lemma 5. Let f Rn beanarbitraryvectorsatisfying: 1. f1 f2 fn 2. Proposition 5.For q = ( c,..., c, 0) Rn withc = 2 Δ logn, theexpectederrorE [ E ( MPF, q)] ofpermute-and-flipisatleastΔ2 log ( n).