8 citations · 41 across the 26 of their papers we have counts for
7 papers · 1 filter
Stochastic and Worst-Case Generalized Sorting Revisited
William Kuszmaul, Shyam Narayanan
The \emph{generalized sorting problem} is a restricted version of standard comparison sorting where we wish to sort elements but only a subset of pairs are allowed to be compar…
Frequency Estimation with One-Sided Error
Piotr Indyk, Shyam Narayanan, David P. Woodruff
Frequency estimation is one of the most fundamental problems in streaming algorithms. Given a stream of elements from some universe , the goal is to compute,…
Tight and Robust Private Mean Estimation with Few Users
Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an -differentially private mechanism using as few users a…
Almost Tight Approximation Algorithms for Explainable Clustering
Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal…
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Shyam Narayanan, Sandeep Silwal, Piotr Indyk +1
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility loca…
Learning-based Support Estimation in Sublinear Time
Talya Eden, Piotr Indyk, Shyam Narayanan +3
We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a ra…
Arithmetic Progressions in Sumsets of Sparse Sets
Noga Alon, Ryan Alweiss, Yang P. Liu +2
A set of positive integers is \emph{log-sparse} if there is an absolute constant so that for any positive integer the sequence contains at most…