Monotonicity testing, routing, and a theorem of Lehman and Ron скачать в хорошем качестве

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

C. Seshadhri https://simons.berkeley.edu/talks/c-s... Workshop on Local Algorithms (WoLA) Monotonicity testing on the hypercube is about as classic as property testing gets, and (as usual) Dana played a central role in the development of this problem. Many of us are probably familiar with her seminal work on this problem. But I'm going to talk about a lesser known result of Dana's; a theorem of Lehman and Ron that connects monotonicity testing and routing on the hypercube. The result itself is a beautiful, independent combinatorial statement about vertex disjoint paths in the hypercube. This theorem played an important role in the development of o(d) monotonicity testers (where d is the hypercube/hypergrid dimension). I will talk about alternate proofs for the Lehman-Ron routing theorem, and a generalized conjecture of this theorem. Regardless of the monotonicity testing connection, I hope to show why Lehman-Ron "style" theorems are fundamental statements about the hypercube. The general Lehman-Ron conjecture gives a different perspective on monotonicity testing, and suggests that efficient property testers are intimately connected to low-congestion flows on the directed hypercube.