Hadley Black

collaborators

2 papers

cs.DS2026

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$ -Monotone Functions

Hadley Black

We study monotonicity testing of functions $f : {0, 1}^{d} \to {0, 1}$ using sample-based algorithms, which are only allowed to observe the value of $f$ on points drawn indepe…

cs.DS2025

A $d^{1/2 + o (1)}$ Monotonicity Tester for Boolean Functions on $d$ -Dimensional Hypergrids

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f : [n]^{d} \to {0, 1}$ , is a classic topic in property testing. Determining the non-adaptive complexity of this problem i…

Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions

A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$ -Monotone Functions

A $d^{1/2 + o (1)}$ Monotonicity Tester for Boolean Functions on $d$ -Dimensional Hypergrids