112 citations · 116 across the 10 of their papers we have counts for
15 papers
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…
Constrained Correlation Clustering: Towards Optimality
Sina Azizeddin, Evangelos Kipouridis, Nithin Varma
In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pa…
Pseudodeterministic Algorithms for Minimum Cut Problems
Aryan Agarwala, Nithin Varma
In this paper, we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global mi…
Testing forbidden order-pattern properties on hypergrids
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg +1
We study testing -freeness of functions , where is -free if there there are no indices such that $f(x_i)<f(x_…
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma
A binary code Enc is -list decodable if for all , the set List of all messages such that the relative H…
(Almost Full) EFX for Three (and More) Types of Agents
Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar +1
We study the problem of determining an envy-free allocation of indivisible goods among multiple agents with additive valuations. EFX, which stands for envy-freeness up to any good,…
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 . Specifically, we present a nonadaptive algor…
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 …
Strongly Sublinear Algorithms for Testing Pattern Freeness
Ilan Newman, Nithin Varma
For a permutation , a function contains a -appearance if there exists such that for all $s,t \in [k…
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…
New Sublinear Algorithms and Lower Bounds for LIS Estimation
Ilan Newman, Nithin Varma
Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the…
Average Sensitivity of Graph Algorithms
Nithin Varma, Yuichi Yoshida
In modern applications of graphs algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full informat…
Bipartite Graphs of Small Readability
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch +4
We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bio…
Erasure-Resilient Property Testing
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta +1
Property testers form an important class of sublinear algorithms. In the standard property testing model, an algorithm accesses the input function via an oracle that returns functi…
Rainbow Connection Number and Connected Dominating Sets
L. Sunil Chandran, Anita Das, Deepak Rajendraprasad +1
Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one…