Nithin M. Varma

activity

20102026

most citedRainbow Connection Number and Connected Dominating Sets

112 citations · 116 across the 10 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021

Parameterized Convexity Testing

Abhiruk Lahiri, Ilan Newman, Nithin Varma

In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain $[n]$ . Specifically, we present a nonadaptive algor…

cs.DS2021

Sublinear-Time Computation in the Presence of Online Erasures

Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma

We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each input query, such an oracle can erase $t$ …

cs.DS2021

Strongly Sublinear Algorithms for Testing Pattern Freeness

Ilan Newman, Nithin Varma

For a permutation $π : [k] \to [k]$ , a function $f : [n] \to R$ contains a $π$ -appearance if there exists $1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n$ such that for all $s,t \in [k…