Dinur and Steuner’s direct product test analysis is very cool.
If
then
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.