Back to search

University of Waterloo

Analytic Property Testing: Directed Isoperimetry and Monotonicity

Abstract

dc:description.abstract

Property testing is a computational paradigm that aims to design algorithms for extremely fast decision-making about massive inputs. Property testing has been studied for nearly three decades, primarily with a focus on testing properties about discrete objects such as Boolean functions and graphs. In this thesis, we study property testing for inherently continuous objects, namely functions with real-valued domain and range---which we call the analytic setting. We study the central problem of monotonicity testing in this setting, where the input is a continuous function f : [0,1]^d → R and the algorithm must decide whether f is monotone with respect to its input coordinates, or far from monotone in the appropriate sense (namely with respect to the L^p distance). The central theme of this thesis is a connection between monotonicity testing and directed isoperimetric inequalities, which are analogues of classical isoperimetric inequalities that have been shown to be intimately related to monotonicity testing in discrete settings. Indeed, many algorithmic advances in monotonicity testing over the last decade have been obtained via new directed isoperimetric inequalities. We show that the connection between directed isoperimetry and monotonicity also holds in the analytic setting, and indeed reveals new relationships between property testing and areas of mathematics such as partial differential equations and optimal transport theory. The main results in this thesis are the directed Poincaré inequality dist^mono_2(f)^2 ≲ E[|∇^- f|^2} for Lipschitz functions f : [0,1]^d → R defined over the solid unit cube, where dist^mono_2(f) denotes the L^2 distance to monotonicity of f and the "directed gradient" operator ∇^- f measures the local violations of monotonicity of f; and a monotonicity tester for this setting with query complexity \widetilde O(\sqrt{d}). We obtain the directed Poincaré inequality by studying a new partial differential equation called the directed heat equation. In our study of monotonicity testing and its connection to directed isoperimetry, we also systematize classical and directed isoperimetric inequalities in continuous and discrete settings; obtain a variety of upper and lower bounds for monotonicity testing of Lipschitz functions in other settings of interest such as the one-dimensional line and the hypergrid; and develop directed Poincaré inequalities for directed graphs by studying a dynamical process called the directed heat flow via directed analogues of classical spectral theory.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ferreira Pinto Junior, Renato

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21947

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ferreira Pinto Junior, Renato. Analytic Property Testing: Directed Isoperimetry and Monotonicity. University of Waterloo, 2025. https://hdl.handle.net/10012/21947