Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
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…
cs.DS2024
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…