5 citations · 6 across the 2 of their papers we have counts for
4 papers
Erasure-Resilient Sublinear-Time Graph Algorithms
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input gra…
Approximating the Distance to Monotonicity of Boolean Functions
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
We design a nonadaptive algorithm that, given oracle access to a function which is -far from monotone, makes poly queries and returns an est…
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
A Boolean function is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadapt…
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
We study the problem of testing unateness of functions We give a -query nonadaptive tester and a -quer…