49 citations · 287 across the 45 of their papers we have counts for
8 papers · 1 filter
Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
Deeparnab Chakrabarty, C. Seshadhri
Motivated by applications to monotonicity testing, Lehman and Ron (JCTA, 2001) proved the existence of a collection of vertex disjoint paths between comparable sub-level sets in th…
Random walks and forbidden minors II: A -query tester for minor-closed properties of bounded-degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
Let be a graph with vertices and maximum degree . Fix some minor-closed property (such as planarity). We say that is -far from $\mathcal{P…
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…
Finding forbidden minors in sublinear time: a -query one-sided tester for minor closed properties on bounded degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
Let be an undirected, bounded degree graph with vertices. Fix a finite graph , and suppose one must remove edges from to make it -minor free (for…
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…
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha +1
The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a not…