49 citations · 287 across the 45 of their papers we have counts for
4 papers · 1 filter
Self-improving Algorithms for Coordinate-Wise Maxima and Convex Hulls
Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri
Finding the coordinate-wise maxima and the convex hull of a planar point set are probably the most classic problems in computational geometry. We consider these problems in the sel…
Self-improving Algorithms for Coordinate-wise Maxima
Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri
Computing the coordinate-wise maxima of a planar point set is a classic and well-studied problem in computational geometry. We give an algorithm for this problem in the \emph{self-…
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
Michael Saks, C. Seshadhri
Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allo…
Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
Deeparnab Chakrabarty, C. Seshadhri
The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given quer…