Improved Monotonicity Testers via Hypercube Embeddings
summary
Shows a distance-preserving embedding that reduces monotonicity testing on product domains (p-biased cubes and hypergrids) to the uniform hypercube, so any hypercube tester yields a tester for the original domain. The reduction simulates queries, controls the dimension blowup, and proves that being far from monotone is preserved, yielding √n query complexity up to polylog factors. Key technical tool is constructing balanced partitions with monotone matchings to handle larger alphabets.
AI-written summary · about
chapters (9)
- 0:00Monotonicity testing intro
- 2:55History of hypercube testers
- 6:26Testing over other domains
- 11:52Reduction for hypergrid
- 14:01Biased to uniform cube
- 20:30Reduction method properties
- 23:23Hypergrid embeddings
- 24:26Concurrent results & questions
- 25:54Future directions
related talks
37mA Bluffer's Guide to Dimension Reduction
39mLocalization and Nonmetric Multidimensional Scaling via Paired Comparisons
19mHow to look at your data
06mMultivariate Visualization of Game Metrics: An Evaluation of Hexbin Maps
38mAdd ALL the things: abstract algebra meets analytics
19mContinuous Arrays
37mPower to the Points: Local Certificates for Clusterings
38mMultidimensional Indexing and Sampling on the Lake