5 papers
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(…
(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,…
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 …