Hadley Black

activity

20172023

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2023

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.DS2022

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $O (n d)$ Monotonicity Tester

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

The problem of testing monotonicity for Boolean functions on the hypergrid, $f : [n]^{d} \to {0, 1}$ is a classic topic in property testing. When $n = 2$ , the domain is the hypercube. F…

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

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an O(nd​) Monotonicity Tester

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

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $O (n d)$ Monotonicity Tester