Dinur and Steuner’s direct product test analysis is very cool.

If

then is -close to a DP.

Analysis:

  • Define .
  • Show it satisfies some monotonicity property; it’s pretty clear that it does
  • Use that to show that there exists some nice with up to
  • Then you can show that conditional on something, a random coordinate is very likely to behave well.
  • Then you can union bound and remove the conditioning and get rid of some other thing
  • Then you do some more stitching.