3 papers
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
Domain Reduction for Monotonicity Testing: A Tester for Boolean Functions in -Dimensions
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
We describe a -query monotonicity tester for Boolean functions on the -hypergrid. This is the first monotonicity tester with que…
cs.DM2017
A Monotonicity Tester for Boolean Functions over the Hypergrid
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
We study monotonicity testing of Boolean functions over the hypergrid and design a non-adaptive tester with -sided error whose query complexity is $\tilde{O}(d^{5/6})\cd…