R. Pallavoor

activity

20162026

most citedTesting Unateness of Real-Valued Functions

14 citations · 20 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

Testing Connectedness and Edge Connectedness

Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1

We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that $ε$ -tes…

cs.DS2020

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…

cs.DS2019

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 $f : {0, 1}^{n} \to {0, 1}$ which is $α$ -far from monotone, makes poly $(n, 1/ α)$ queries and returns an est…

cs.DS2017★ 1 cited

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 $f : {0, 1}^{d} \to R .$ We give a $O (\frac{d}{ε} \cdot lo g \frac{d}{ε})$ -query nonadaptive tester and a $O (\frac{d}{ε})$ -quer…

cs.DS2016★ 14 cited

Testing Unateness of Real-Valued Functions

Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor +1

We give a unateness tester for functions of the form $f : [n]^{d} \to R$ , where $n, d \in N$ and $R \subseteq R$ with query complexity $O(\frac{d\log (\max(d,n))}…