research
∙
05/04/2023
Testing Convexity of Discrete Sets in High Dimensions
We study the problem of testing whether an unknown set S in n dimensions...
share
research
∙
04/03/2023
A d^1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
Monotonicity testing of Boolean functions on the hypergrid, f:[n]^d →{0,...
research
∙
11/10/2022
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an O(n√(d)) Monotonicity Tester
The problem of testing monotonicity for Boolean functions on the hypergr...
research
∙
11/18/2020
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing
We generalize the celebrated isoperimetric inequality of Khot, Minzer, a...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
We describe a Õ(d^5/6)-query monotonicity tester for Boolean functions f...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids
Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d →{...
research
∙
10/29/2017