Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. - Shyam Narayanan (APPROX-RANDOM, 2018)

The 26 Wilf-equivalence classes of length five quasi-consecutive patterns. - Evan Chen; Shyam Narayanan (Discret. Math. Theor. Comput. Sci., 2018)

Pairwise Independent Random Walks Can Be Slightly Unbounded. - Shyam Narayanan (APPROX-RANDOM, 2019)

Optimal terminal dimensionality reduction in Euclidean space. - Shyam Narayanan; Jelani Nelson (STOC, 2019)

Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds. - Shyam Narayanan (CoRR, 2020)

Functions that Preserve Manhattan Distances. - Timothy Chu; Gary L. Miller; Shyam Narayanan; Mark Sellke (CoRR, 2020)

Functions on antipower prefix lengths of the Thue-Morse word. - Shyam Narayanan (Discret. Math., 2020)

Stochastic and Worst-Case Generalized Sorting Revisited. - William Kuszmaul; Shyam Narayanan (FOCS, 2021)

Learning-based Support Estimation in Sublinear Time. - Talya Eden; Piotr Indyk; Shyam Narayanan; Ronitt Rubinfeld; Sandeep Silwal; Tal Wagner (ICLR, 2021)

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering. - Shyam Narayanan; Sandeep Silwal; Piotr Indyk; Or Zamir (ICML, 2021)

Circular Trace Reconstruction. - Shyam Narayanan; Michael Ren (ITCS, 2021)

On Tolerant Distribution Testing in the Conditional Sampling Model. - Shyam Narayanan (SODA, 2021)

Improved Algorithms for Population Recovery from the Deletion Channel. - Shyam Narayanan (SODA, 2021)

Bounds on expected propagation time of probabilistic zero forcing. - Shyam Narayanan; Alec Sun (Eur. J. Comb., 2021)

Private High-Dimensional Hypothesis Testing. - Shyam Narayanan (COLT, 2022)

Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. - William Kuszmaul; Shyam Narayanan (ICALP, 2022)

Triangle and Four Cycle Counting with Predictions in Graph Streams. - Justin Y. Chen; Talya Eden; Piotr Indyk; Honghao Lin; Shyam Narayanan; Ronitt Rubinfeld; Sandeep Silwal; Tal Wagner; David P. Woodruff; Michael Zhang (ICLR, 2022)

Tight and Robust Private Mean Estimation with Few Users. - Shyam Narayanan; Vahab S. Mirrokni; Hossein Esfandiari (ICML, 2022)

Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems. - Matteo Cartiglia; Arianna Rubino; Shyam Narayanan; Charlotte Frenkel; Germain Haessig; Giacomo Indiveri; Melika Payvand (ISCAS, 2022)

A 120dB Programmable-Range On-Chip Pulse Generator for Characterizing Ferroelectric Devices. - Shyam Narayanan; Erika Covi; Viktor Havel; Charlotte Frenkel; Suzanne Lancaster; Quang T. Duong; Stefan Slesazeck; Thomas Mikolajick; Melika Payvand; Giacomo Indiveri (ISCAS, 2022)

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. - Anders Aamand; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Ronitt Rubinfeld; Nicholas Schiefer; Sandeep Silwal; Tal Wagner (NeurIPS, 2022)

Near-Optimal Private and Scalable $k$-Clustering. - Vincent Cohen-Addad; Alessandro Epasto; Vahab Mirrokni; Shyam Narayanan; Peilin Zhong (NeurIPS, 2022)

Almost Tight Approximation Algorithms for Explainable Clustering. - Hossein Esfandiari; Vahab S. Mirrokni; Shyam Narayanan (SODA, 2022)

Frequency Estimation with One-Sided Error. - Piotr Indyk; Shyam Narayanan; David P. Woodruff (SODA, 2022)

Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. - Vincent Cohen-Addad; Hossein Esfandiari; Vahab S. Mirrokni; Shyam Narayanan (STOC, 2022)

All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights. - Justin Y. Chen; Shyam Narayanan; Yinzhan Xu (CoRR, 2022)

Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. - Vincent Cohen-Addad; Hossein Esfandiari; Vahab S. Mirrokni; Shyam Narayanan (CoRR, 2022)

Three-wise independent random walks can be slightly unbounded. - Shyam Narayanan (Random Struct. Algorithms, 2022)

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees. - Nicholas Schiefer; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Sandeep Silwal; Tal Wagner (ACDA, 2023)

Bias Reduction for Sum Estimation. - Talya Eden; Jakob Bæk Tejs Houen; Shyam Narayanan; Will Rosenbaum; Jakub Tetek (APPROX/RANDOM, 2023)

Improved Diversity Maximization Algorithms for Matching and Pseudoforest. - Sepideh Mahabadi; Shyam Narayanan (APPROX/RANDOM, 2023)

SPAIC: A sub-μW/Channel, 16-Channel General-Purpose Event-Based Analog Front-End with Dual-Mode Encoders. - Shyam Narayanan; Matteo Cartiglia; Arianna Rubino; Charles Lego; Charlotte Frenkel; Giacomo Indiveri (BioCAS, 2023)

Krylov Methods are (nearly) Optimal for Low-Rank Approximation. - Ainesh Bakshi; Shyam Narayanan (FOCS, 2023)

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. - Clément L. Canonne; Samuel B. Hopkins 001; Jerry Li 001; Allen Liu; Shyam Narayanan (FOCS, 2023)

Data Structures for Density Estimation. - Anders Aamand; Alexandr Andoni; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Sandeep Silwal (ICML, 2023)

Differentially Private Approximate Near Neighbor Counting in High Dimensions. - Alexandr Andoni; Piotr Indyk; Sepideh Mahabadi; Shyam Narayanan (NeurIPS, 2023)

k-Means Clustering with Distance-Based Privacy. - Alessandro Epasto; Vahab Mirrokni; Shyam Narayanan; Peilin Zhong (NeurIPS, 2023)

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. - Justin Y. Chen; Badih Ghazi; Ravi Kumar 001; Pasin Manurangsi; Shyam Narayanan; Jelani Nelson; Yinzhan Xu (SODA, 2023)

Sampling an Edge in Sublinear Time Exactly and Optimally. - Talya Eden; Shyam Narayanan; Jakub Tetek (SOSA, 2023)

Estimating the Effective Support Size in Constant Query Complexity. - Shyam Narayanan; Jakub Tetek (SOSA, 2023)

Robustness Implies Privacy in Statistical Estimation. - Samuel B. Hopkins 001; Gautam Kamath 001; Mahbod Majid; Shyam Narayanan (STOC, 2023)

A faster and simpler algorithm for learning shallow networks. - Sitan Chen; Shyam Narayanan (COLT, 2024)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation. - Shyam Narayanan; Václav Rozhon; Jakub Tetek; Mikkel Thorup (FOCS, 2024)

Statistical-Computational Trade-offs for Density Estimation. - Anders Aamand; Alexandr Andoni; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Sandeep Silwal; Haike Xu (NeurIPS, 2024)

Sample-Efficient Private Learning of Mixtures of Gaussians. - Hassan Ashtiani; Mahbod Majid; Shyam Narayanan (NeurIPS, 2024)

Metric Transforms and Low Rank Representations of Kernels for Fast Attention. - Timothy Chu; Josh Alman; Gary L. Miller; Shyam Narayanan; Mark Sellke; Zhao Song 002 (NeurIPS, 2024)

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree. - Rajesh Jayaram; Vahab Mirrokni; Shyam Narayanan; Peilin Zhong (SODA, 2024)

Query Lower Bounds for Log-concave Sampling. - Sinho Chewi; Jaume de Dios Pont; Jerry Li 001; Chen Lu 002; Shyam Narayanan (J. ACM, 2024)

Improved algorithms for learning quantum Hamiltonians, via flat polynomials. - Shyam Narayanan (COLT, 2025)

Near-Optimal Trace Reconstruction for Mildly Separated Strings. - Anders Aamand; Allen Liu; Shyam Narayanan (ICALP, 2025)

Live Demonstration: A real-time event encoder for seizure monitoring on Neuromorphic Hardware. - Saptarshi Ghosh 003; Olympia Gallou; Shyam Narayanan; Jim Bartels; Giacomo Indiveri (ISCAS, 2025)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation. - Shyam Narayanan (IEEE Trans. Inf. Theory, 2025)

On the Structure of Replicable Hypothesis Testers. - Anders Aamand; Maryam Aliakbarpour; Justin Y. Chen; Shyam Narayanan; Sandeep Silwal (CoRR, 2025)