112 citations · 116 across the 10 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
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…
cs.DS2020
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…