8 citations · 41 across the 26 of their papers we have counts for
39 papers
Local Search for Fair Max-Min Diversification
Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar
Given points in a metric space, Max-Min diversification asks for a subset of points maximizing the minimum pairwise distance between the selected points. This is arguably t…
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set of points, the goal i…
A faster and simpler algorithm for learning shallow networks
Sitan Chen, Shyam Narayanan
We revisit the well-studied problem of learning a linear combination of ReLU activations given labeled examples drawn from the standard -dimensional Gaussian measure. Chen e…
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li +2
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samp…
Improved Diversity Maximization Algorithms for Matching and Pseudoforest
Sepideh Mahabadi, Shyam Narayanan
In this work we consider the diversity maximization problem, where given a data set of elements, and a parameter , the goal is to pick a subset of of size maximi…
Data Structures for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +3
We study statistical/computational tradeoffs for the following density estimation problem: given distributions over a discrete domain of size , and sampli…
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3
An -approximate quantile sketch over a stream of inputs approximates the rank of any query point - that is, the number of input points less than - up to an…
Krylov Methods are (nearly) Optimal for Low-Rank Approximation
Ainesh Bakshi, Shyam Narayanan
We consider the problem of rank- low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: $$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal…
Query lower bounds for log-concave sampling
Sinho Chewi, Jaume de Dios Pont, Jerry Li +2
Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with l…
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Anders Aamand, Justin Y. Chen, Piotr Indyk +5
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph…
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid +1
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to…
Estimating the Effective Support Size in Constant Query Complexity
Shyam Narayanan, Jakub Tětek
Estimating the support size of a distribution is a well-studied problem in statistics. Motivated by the fact that this problem is highly non-robust (as small perturbations in the d…
Sampling an Edge in Sublinear Time Exactly and Optimally
Talya Eden, Shyam Narayanan, Jakub Tětek
Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of…
Bias Reduction for Sum Estimation
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2
In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution , and that when an element is sampled, the probabil…
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
William Kuszmaul, Shyam Narayanan
The \emph{-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a -processor machine must assign tasks to processors ove…
Improved Approximations for Euclidean -means and -median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni +1
Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean -median and -means problems. We propose a new primal-dual alg…
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
Justin Y. Chen, Shyam Narayanan, Yinzhan Xu
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea…
Triangle and Four Cycle Counting with Predictions in Graph Streams
Justin Y. Chen, Talya Eden, Piotr Indyk +7
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in…
Private High-Dimensional Hypothesis Testing
Shyam Narayanan
We provide improved differentially private algorithms for identity testing of high-dimensional distributions. Specifically, for -dimensional Gaussian distributions with known co…
A 120dB Programmable-Range On-Chip Pulse Generator for Characterizing Ferroelectric Devices
Shyam Narayanan, Erika Covi, Viktor Havel +7
Novel non-volatile memory devices based on ferroelectric thin films represent a promising emerging technology that is ideally suited for neuromorphic applications. The physical swi…
Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems
Matteo Cartiglia, Arianna Rubino, Shyam Narayanan +4
The stringent memory and power constraints required in edge-computing sensory-processing applications have made event-driven neuromorphic systems a promising technology. On-chip on…
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…