7 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(x_…
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…
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…