49 citations · 287 across the 45 of their papers we have counts for
53 papers
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
Deeparnab Chakrabarty, Xi Chen, Simeon Ristic +2
We study monotonicity testing of high-dimensional distributions on in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~\cite{CRS1…
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…
A Monotonicity Tester for Boolean Functions on -Dimensional Hypergrids
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
Monotonicity testing of Boolean functions on the hypergrid, , is a classic topic in property testing. Determining the non-adaptive complexity of this problem i…
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Monotonicity Tester
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
The problem of testing monotonicity for Boolean functions on the hypergrid, is a classic topic in property testing. When , the domain is the hypercube. F…
A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
Daniel Paul-Pena, C. Seshadhri
Counting the number of homomorphisms of a pattern graph H in a large input graph G is a fundamental problem in computer science. There are myriad applications of this problem in da…
Spectral Triadic Decompositions of Real-World Networks
Sabyasachi Basu, Suman Kalyan Bera, C. Seshadhri
A fundamental problem in mathematics and network analysis is to find conditions under which a graph can be partitioned into smaller pieces. The most important tool for this partiti…