4 papers · 1 filter
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(…
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 …