Hadley Black

activity

20172023

most citedDomain Reduction for Monotonicity Testing: A

o (d)

Tester for Boolean Functions in

d

-Dimensions

2 citations · 3 across the 4 of their papers we have counts for

collaborators

7 papers

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

Testing and Learning Convex Sets in the Ternary Hypercube

Hadley Black, Eric Blais, Nathaniel Harms

We study the problems of testing and learning high-dimensional discrete convex sets. The simplest high-dimensional discrete domain where convexity is a non-trivial property is the…

cs.DS2023★ 1 cited

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…

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…

cs.DM2020

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra~(SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mat…

cs.DM2018★ 2 cited

Domain Reduction for Monotonicity Testing: A $o (d)$ Tester for Boolean Functions in $d$ -Dimensions

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We describe a $O ~ (d^{5/6})$ -query monotonicity tester for Boolean functions $f : [n]^{d} \to {0, 1}$ on the $n$ -hypergrid. This is the first $o (d)$ monotonicity tester with que…

cs.DM2017

A $o (d) \cdot polylog n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^{d}$

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^{d}$ and design a non-adaptive tester with $1$ -sided error whose query complexity is $\tilde{O}(d^{5/6})\cd…

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

Testing and Learning Convex Sets in the Ternary Hypercube

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

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

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions

A o(d)⋅polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d

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

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

Domain Reduction for Monotonicity Testing: A $o (d)$ Tester for Boolean Functions in $d$ -Dimensions

A $o (d) \cdot polylog n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^{d}$