Monotonicity Testing, Routing, and the Lehman-Ron Theorem on Hypercube Properties

Explore a 32-minute conference talk by C. Seshadhri at the Simons Institute's Workshop on Local Algorithms (WoLA). Delve into the fascinating world of monotonicity testing on the hypercube, focusing on a lesser-known theorem by Lehman and Ron that connects monotonicity testing and routing. Discover how this theorem, which deals with vertex disjoint paths in the hypercube, has significantly influenced the development of o(d) monotonicity testers. Examine alternative proofs for the Lehman-Ron routing theorem and consider a generalized conjecture. Gain insights into why Lehman-Ron "style" theorems are fundamental to understanding the hypercube structure. Explore the relationship between efficient property testers and low-congestion flows on the directed hypercube, offering a fresh perspective on monotonicity testing.

Monotonicity testing, routing, and a theorem of Lehman and Ron