Shyam Narayanan

92 papers A* 32A 3C 3Journal 48Unranked 6

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