Shyam Narayanan

According to our database, Shyam Narayanan authored at least 48 papers between 2018 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Query Lower Bounds for Log-concave Sampling.

Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan

J. ACM, August, 2024

Statistical-Computational Trade-offs for Density Estimation.

Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu

CoRR, 2024

Improved algorithms for learning quantum Hamiltonians, via flat polynomials.

Shyam Narayanan

CoRR, 2024

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree.

Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation.

Shyam Narayanan, Václav Rozhon, Jakub Tetek, Mikkel Thorup

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

A faster and simpler algorithm for learning shallow networks.

Sitan Chen, Shyam Narayanan

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation.

Shyam Narayanan

CoRR, 2023

Robustness Implies Privacy in Statistical Estimation.

Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Estimating the Effective Support Size in Constant Query Complexity.

Shyam Narayanan, Jakub Tetek

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Sampling an Edge in Sublinear Time Exactly and Optimally.

Talya Eden, Shyam Narayanan, Jakub Tetek

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds.

Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

k-Means Clustering with Distance-Based Privacy.

Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Differentially Private Approximate Near Neighbor Counting in High Dimensions.

Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Data Structures for Density Estimation.

Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal

Proceedings of the International Conference on Machine Learning, 2023

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination.

Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Krylov Methods are (nearly) Optimal for Low-Rank Approximation.

Ainesh Bakshi, Shyam Narayanan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 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

Proceedings of the IEEE Biomedical Circuits and Systems Conference, 2023

Improved Diversity Maximization Algorithms for Matching and Pseudoforest.

Sepideh Mahabadi, Shyam Narayanan

Proceedings of the Approximation, 2023

Bias Reduction for Sum Estimation.

Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, Jakub Tetek

Proceedings of the Approximation, 2023

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees.

Nicholas Schiefer, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Tal Wagner

Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms, 2023

2022

Three-wise independent random walks can be slightly unbounded.

Shyam Narayanan

Random Struct. Algorithms, 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

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 <i>k</i>-means and <i>k</i>-median, via nested quasi-independent sets.

Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Frequency Estimation with One-Sided Error.

Piotr Indyk, Shyam Narayanan, David P. Woodruff

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Almost Tight Approximation Algorithms for Explainable Clustering.

Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Private and Scalable $k$-Clustering.

Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 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

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 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

Proceedings of the IEEE International Symposium on Circuits and Systems, 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

Proceedings of the IEEE International Symposium on Circuits and Systems, 2022

Tight and Robust Private Mean Estimation with Few Users.

Shyam Narayanan, Vahab S. Mirrokni, Hossein Esfandiari

Proceedings of the International Conference on Machine Learning, 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

Proceedings of the Tenth International Conference on Learning Representations, 2022

Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game.

William Kuszmaul, Shyam Narayanan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Private High-Dimensional Hypothesis Testing.

Shyam Narayanan

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Bounds on expected propagation time of probabilistic zero forcing.

Shyam Narayanan, Alec Sun

Eur. J. Comb., 2021

Improved Algorithms for Population Recovery from the Deletion Channel.

Shyam Narayanan

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On Tolerant Distribution Testing in the Conditional Sampling Model.

Shyam Narayanan

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Circular Trace Reconstruction.

Shyam Narayanan, Michael Ren

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering.

Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir

Proceedings of the 38th International Conference on Machine Learning, 2021

Learning-based Support Estimation in Sublinear Time.

Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner

Proceedings of the 9th International Conference on Learning Representations, 2021

Stochastic and Worst-Case Generalized Sorting Revisited.

William Kuszmaul, Shyam Narayanan

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Functions on antipower prefix lengths of the Thue-Morse word.

Shyam Narayanan

Discret. Math., 2020

Functions that Preserve Manhattan Distances.

Timothy Chu, Gary L. Miller, Shyam Narayanan, Mark Sellke

CoRR, 2020

Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds.

Shyam Narayanan

CoRR, 2020

2019

Optimal terminal dimensionality reduction in Euclidean space.

Shyam Narayanan, Jelani Nelson

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Pairwise Independent Random Walks Can Be Slightly Unbounded.

Shyam Narayanan

Proceedings of the Approximation, 2019

2018

The 26 Wilf-equivalence classes of length five quasi-consecutive patterns.

Evan Chen, Shyam Narayanan

Discret. Math. Theor. Comput. Sci., 2018

Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers.

Shyam Narayanan

Proceedings of the Approximation, 2018