Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach

This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and mono-tonicity testing. We study the setting of real-valued functions <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f:[0, 1]^{d}\rightarrow\mathbb{R}$</tex> on the solid unit cube, where the goal is to test with respect to the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$L^{p}$</tex> distance. Ourgoals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting, Our main results are 1) an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$L^{2}$</tex> monotonicity tester for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex>-Lipschitz functions with query complexity <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\sqrt{d}M^{2}/\varepsilon^{2})$</tex> and, behind this result, 2) the directed Poincaré inequality <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{dist}_{2}^{\text{mono}}(f)^{2}\leq C\mathbb{E}\Vert \nabla^{-}f\vert^{2}]$</tex>, where the “directed gradient” operator <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\nabla{-}$</tex> measures the local violations of monotonicity of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex>. To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> into a monotone function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f^{*}$</tex> over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.