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