Shyam Narayanan

Publication Activity (10 Years)

Years Active: 2018-2024
Publications (10 Years): 79

Top Topics

Statistical Estimation

Hypothesis Test

Improved Algorithm

Top Venues

Publications

Sitan Chen, Shyam Narayanan
A faster and simpler algorithm for learning shallow networks. COLT (2024)
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree. SODA (2024)
Shyam Narayanan
Improved algorithms for learning quantum Hamiltonians, via flat polynomials. CoRR (2024)
Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan
Query Lower Bounds for Log-concave Sampling. J. ACM 71 (4) (2024)
Sepideh Mahabadi, Shyam Narayanan
Improved Diversity Maximization Algorithms for Matching and Pseudoforest. APPROX/RANDOM (2023)
Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan
Differentially Private Approximate Near Neighbor Counting in High Dimensions. NeurIPS (2023)
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree. CoRR (2023)
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Tal Wagner
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees. CoRR (2023)
Shyam Narayanan, Jakub Tetek
Estimating the Effective Support Size in Constant Query Complexity. SOSA (2023)
Talya Eden, Shyam Narayanan, Jakub Tetek
Sampling an Edge in Sublinear Time Exactly and Optimally. SOSA (2023)
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan
Robustness Implies Privacy in Statistical Estimation. STOC (2023)
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. FOCS (2023)
Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan
Query lower bounds for log-concave sampling. CoRR (2023)
Sitan Chen, Shyam Narayanan
A faster and simpler algorithm for learning shallow networks. CoRR (2023)
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. CoRR (2023)
Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan
Query lower bounds for log-concave sampling. FOCS (2023)
Shyam Narayanan
Better and Simpler Lower Bounds for Differentially Private Statistical Estimation. CoRR (2023)
Sepideh Mahabadi, Shyam Narayanan
Improved Diversity Maximization Algorithms for Matching and Pseudoforest. CoRR (2023)
Shyam Narayanan, Matteo Cartiglia, Arianna Rubino, Charles Lego, Charlotte Frenkel, Giacomo Indiveri
SPAIC: A sub-μW/Channel, 16-Channel General-Purpose Event-Based Analog Front-End with Dual-Mode Encoders. CoRR (2023)
Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
Data Structures for Density Estimation. CoRR (2023)
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, Jakub Tetek
Bias Reduction for Sum Estimation. APPROX/RANDOM (2023)
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Tal Wagner
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees. ACDA (2023)
Ainesh Bakshi, Shyam Narayanan
Krylov Methods are (nearly) Optimal for Low-Rank Approximation. CoRR (2023)
Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
Data Structures for Density Estimation. ICML (2023)
Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. SODA (2023)
Shyam Narayanan, Matteo Cartiglia, Arianna Rubino, Charles Lego, Charlotte Frenkel, Giacomo Indiveri
SPAIC: A sub-μW/Channel, 16-Channel General-Purpose Event-Based Analog Front-End with Dual-Mode Encoders. BioCAS (2023)
Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
k-Means Clustering with Distance-Based Privacy. NeurIPS (2023)
Ainesh Bakshi, Shyam Narayanan
Krylov Methods are (nearly) Optimal for Low-Rank Approximation. FOCS (2023)
Shyam Narayanan, Erika Covi, Viktor Havel, Charlotte Frenkel, Suzanne Lancaster, Quang T. Duong, Stefan Slesazeck, Thomas Mikolajick, Melika Payvand, Giacomo Indiveri
A 120dB Programmable-Range On-Chip Pulse Generator for Characterizing Ferroelectric Devices. CoRR (2022)
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan
Robustness Implies Privacy in Statistical Estimation. CoRR (2022)
Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. CoRR (2022)
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR (2022)
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR (2022)
Shyam Narayanan, Jakub Tetek
Estimating the Effective Support Size in Constant Query Complexity. CoRR (2022)
Piotr Indyk, Shyam Narayanan, David P. Woodruff
Frequency Estimation with One-Sided Error. SODA (2022)
Matteo Cartiglia, Arianna Rubino, Shyam Narayanan, Charlotte Frenkel, Germain Haessig, Giacomo Indiveri, Melika Payvand
Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems. CoRR (2022)
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR (2022)
Talya Eden, Shyam Narayanan, Jakub Tetek
Sampling an Edge in Sublinear Time Exactly and Optimally. CoRR (2022)
Shyam Narayanan, Erika Covi, Viktor Havel, Charlotte Frenkel, Suzanne Lancaster, Quang T. Duong, Stefan Slesazeck, Thomas Mikolajick, Melika Payvand, Giacomo Indiveri
A 120dB Programmable-Range On-Chip Pulse Generator for Characterizing Ferroelectric Devices. ISCAS (2022)
William Kuszmaul, Shyam Narayanan
Stochastic and Worst-Case Generalized Sorting Revisited. FOCS (2022)
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, Jakub Tetek
Bias Reduction for Sum Estimation. CoRR (2022)
Shyam Narayanan
Private High-Dimensional Hypothesis Testing. CoRR (2022)
Justin Y. Chen, Shyam Narayanan, Yinzhan Xu
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights. CoRR (2022)
William Kuszmaul, Shyam Narayanan
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. ICALP (2022)
William Kuszmaul, Shyam Narayanan
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. CoRR (2022)
Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
Near-Optimal Private and Scalable $k$-Clustering. NeurIPS (2022)
Shyam Narayanan, Vahab S. Mirrokni, Hossein Esfandiari
Tight and Robust Private Mean Estimation with Few Users. ICML (2022)
Shyam Narayanan
Private High-Dimensional Hypothesis Testing. COLT (2022)
Shyam Narayanan
Three-wise independent random walks can be slightly unbounded. Random Struct. Algorithms 61 (3) (2022)
Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
Almost Tight Approximation Algorithms for Explainable Clustering. SODA (2022)
Matteo Cartiglia, Arianna Rubino, Shyam Narayanan, Charlotte Frenkel, Germain Haessig, Giacomo Indiveri, Melika Payvand
Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems. ISCAS (2022)
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
-median, via nested quasi-independent sets. STOC (2022)
Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. NeurIPS (2022)
Shyam Narayanan
Improved Algorithms for Population Recovery from the Deletion Channel. SODA (2021)
Shyam Narayanan, Alec Sun
Bounds on expected propagation time of probabilistic zero forcing. Eur. J. Comb. 98 (2021)
Piotr Indyk, Shyam Narayanan, David P. Woodruff
Frequency Estimation with One-Sided Error. CoRR (2021)
William Kuszmaul, Shyam Narayanan
Stochastic and Worst-Case Generalized Sorting Revisited. CoRR (2021)
William Kuszmaul, Shyam Narayanan
Stochastic and Worst-Case Generalized Sorting Revisited. FOCS (2021)
Shyam Narayanan
On Tolerant Distribution Testing in the Conditional Sampling Model. SODA (2021)
Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering. ICML (2021)
Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
Almost Tight Approximation Algorithms for Explainable Clustering. CoRR (2021)
Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering. CoRR (2021)
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner
Learning-based Support Estimation in Sublinear Time. CoRR (2021)
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner
Learning-based Support Estimation in Sublinear Time. ICLR (2021)
Shyam Narayanan, Michael Ren
Circular Trace Reconstruction. ITCS (2021)
Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
Tight and Robust Private Mean Estimation with Few Users. CoRR (2021)
Shyam Narayanan
Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds. CoRR (2020)
Shyam Narayanan
Tolerant Distribution Testing in the Conditional Sampling Model. CoRR (2020)
Shyam Narayanan
Functions on antipower prefix lengths of the Thue-Morse word. Discret. Math. 343 (2) (2020)
Shyam Narayanan, Michael Ren
Circular Trace Reconstruction. CoRR (2020)
Timothy Chu, Gary L. Miller, Shyam Narayanan, Mark Sellke
Functions that Preserve Manhattan Distances. CoRR (2020)
Shyam Narayanan
Pairwise Independent Random Walks Can Be Slightly Unbounded. APPROX-RANDOM (2019)
Shyam Narayanan, Alec Sun
Bounds on expected propagation time of probabilistic zero forcing. CoRR (2019)
Shyam Narayanan, Jelani Nelson
Optimal terminal dimensionality reduction in Euclidean space. STOC (2019)
Shyam Narayanan
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. APPROX-RANDOM (2018)
Shyam Narayanan
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. CoRR (2018)
Evan Chen, Shyam Narayanan
The 26 Wilf-equivalence classes of length five quasi-consecutive patterns. Discret. Math. Theor. Comput. Sci. 20 (2) (2018)
Shyam Narayanan, Jelani Nelson
Optimal terminal dimensionality reduction in Euclidean space. CoRR (2018)
Shyam Narayanan
Pairwise Independent Random Walks can be Slightly Unbounded. CoRR (2018)