Publications

Testing and Learning Distributions

• Shyam Narayanan. Better and Simpler Lower Bounds for Differentially Private Statistical Estimation. Manuscript.

  • • https://arxiv.org/abs/2310.06289

• Sitan Chen and Shyam Narayanan. A faster and simpler algorithm for learning shallow networks. Manuscript.

  • • https://arxiv.org/abs/2307.12496

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

  • • Invited to the SIAM Journal on Computing (SICOMP) Special Issue for FOCS 2023

    • https://arxiv.org/abs/2307.10273

• Talya Eden, Jakob Houen, Shyam Narayanan, Will Rosenbaum, and Jakub Tetek. Bias Reduction for Sum Estimation. International Conference on Randomization and Computation (RANDOM), 2023.

  • • https://arxiv.org/abs/2208.01197

• Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, and Sandeep Silwal. Data Structures for Density Estimation. International Conference on Machine Learning (ICML), 2023.

  • • https://arxiv.org/abs/2306.11312

• Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness Implies Privacy in Statistical Estimation. Symposium on Theory of Computing (STOC), 2023.

  • • Oral Presentation at Theory and Practice of Differential Privacy (TPDP), 2023

    • https://arxiv.org/abs/2212.05015

• Shyam Narayanan and Jakub Tetek. Estimating the Effective Support Size in Constant Query Complexity. Symposium on Simplicity in Algorithms (SOSA), 2023.

  • • https://arxiv.org/abs/2211.11344

    • Answers an open problem from sublinear.info

• Shyam Narayanan. Private High-Dimensional Hypothesis Testing. Conference on Learning Theory (COLT), 2022.

  • • https://arxiv.org/abs/2203.01537

    • Featured in Property Testing Review

• Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Tight and Robust Private Mean Estimation with Few Users. International Conference on Machine Learning (ICML), 2022.

  • • Long Talk at ICML 2022

    • https://arxiv.org/abs/2110.11876

• Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based Support Estimation in Sublinear Time. International Conference on Learning Representations (ICLR), 2021.

  • • Spotlight Presentation at ICLR 2021

    • https://arxiv.org/abs/2106.08396

    • Featured in Property Testing Review

• Shyam Narayanan and Michael Ren. Circular Trace Reconstruction. Innovations in Theoretical Computer Science (ITCS), 2021. 

  • • https://arxiv.org/abs/2009.01346

• Shyam Narayanan. On Tolerant Distribution Testing in the Conditional Sampling Model. Symposium on Discrete Algorithms (SODA), 2021. 

  • • https://arxiv.org/abs/2007.09895

    • Featured in Property Testing Review

• Shyam Narayanan. Improved Algorithms for Population Recovery from the Deletion Channel. Symposium on Discrete Algorithms (SODA), 2021. 

  • • https://arxiv.org/abs/2004.06828

Clustering and High-Dimensional Data

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

  • • https://arxiv.org/abs/2308.00503

• Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, and Shyam Narayanan. Differentially Private Approximate Near Neighbor Counting in High Dimensions. Neural Information Processing Systems (NeurIPS), 2023.

  • • Spotlight Presentation at NeurIPS 2023.

    • https://openreview.net/forum?id=Zt9RzHjSEy

• Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. k-Means Clustering with Distance-Based Privacy. Neural Information Processing Systems (NeurIPS), 2023.

  • • https://openreview.net/forum?id=UzUhiKACmS

• Sepideh Mahabadi and Shyam Narayanan. Improved Diversity Maximization Algorithms for Matching and Pseudoforest. International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2023.

  • • https://arxiv.org/abs/2307.04329 

• Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Near-Optimal Private and Scalable k-Clustering. Neural Information Processing Systems (NeurIPS), 2022.

  • • Oral Presentation at NeurIPS 2022

    • https://openreview.net/pdf?id=9lQmaKMxIUD

• Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. Symposium on Theory of Computing (STOC), 2022.

  • • https://arxiv.org/abs/2204.04828

• Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Almost Tight Approximation Algorithms for Explainable Clustering. Symposium on Discrete Algorithms (SODA), 2022.

  • • https://arxiv.org/abs/2107.00774

• Shyam Narayanan*, Sandeep Silwal*, Piotr Indyk, and Or Zamir. Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering. International Conference on Machine Learning (ICML), 2021.

  • • https://arxiv.org/abs/2107.01804

• Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in Euclidean space. Symposium on Theory of Computing (STOC), 2019. 

  • • https://arxiv.org/abs/1810.09250

• Shyam Narayanan. Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2018. 

  • • https://arxiv.org/abs/1806.07356

Sublinear Algorithms, etc.

• Ainesh Bakshi and Shyam Narayanan. Krylov Methods are (nearly) Optimal for Low-Rank Approximation. Foundations of Computer Science (FOCS), 2023.

  • • https://arxiv.org/abs/2304.03191

• Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan. Query lower bounds for log-concave sampling. Foundations of Computer Science (FOCS), 2023.

  • • https://arxiv.org/abs/2304.02599

• Nicholas Schiefer*, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, and Tal Wagner. Learned Interpolation for Better Streaming Quantile Approximation with Worst Case Guarantees. Applied and Computational Discrete Algorithms (ACDA), 2023.

  • • https://arxiv.org/abs/2304.07652

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

  • • Merger of two papers: Chen, Narayanan, and Xu (https://arxiv.org/abs/2204.02335) and Ghazi, Kumar, Manurangsi, and Nelson (https://arxiv.org/abs/2203.16476).

    • Answers an open problem from differentialprivacy.org

• Talya Eden, Shyam Narayanan, and Jakub Tetek. Sampling an Edge in Sublinear Time Exactly and Optimally. Symposium on Simplicity in Algorithms (SOSA), 2023.

  • • https://arxiv.org/abs/2211.04981

    • Featured in Property Testing Review

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

  • • https://arxiv.org/abs/2203.09572

• Piotr Indyk, Shyam Narayanan, and David P. Woodruff. Frequency Estimation with One-Sided Error. Symposium on Discrete Algorithms (SODA), 2022.

  • • https://arxiv.org/abs/2111.03953

• William Kuszmaul and Shyam Narayanan. Stochastic and Worst-case Generalized Sorting Revisited. Foundations of Computer Science (FOCS), 2021.

  • • Invited talk (by Bill) at Highlights of Algorithms (HALG), 2022.

    • https://arxiv.org/abs/2111.07222

Combinatorics and Discrete Probability

• Shyam Narayanan. 3-Wise Independent Random Walks can be Slightly Unbounded. Random Structures and Algorithms, 2022.

  • • https://arxiv.org/abs/1807.04910 

    • Preliminary version in International Conference on Randomization and Computation (RANDOM), 2019.

• Noga Alon, Ryan Alweiss, Yang P. Liu, Anders Martinsson, Shyam Narayanan. Arithmetic Progressions in Sumsets of Sparse Sets. Integers: Ron Graham Memorial Volume, 2021.

  • • https://arxiv.org/pdf/2104.01564.pdf

• Shyam Narayanan and Alec Sun. Bounds on expected propagation time of probabilistic zero forcing. European Journal of Combinatorics, 2021.

  • • https://arxiv.org/abs/1909.04482

• Shyam Narayanan. Functions on Antipower Prefix Lengths of the Thue-Morse Word. Discrete Mathematics, 2020.

  • • https://arxiv.org/abs/1705.06310

• Shyam Narayanan. Resolving Two Conjectures on Staircase Encodings and Boundary Grids of 132 and 123-avoiding permutations. Electronic Journal of Combinatorics, 2019.

  • • https://arxiv.org/abs/1802.06345

• Evan Chen and Shyam Narayanan. The 26 Wilf-equivalence classes of length five quasi-consecutive patterns. Discrete Mathematics and Theoretical Computer Science, 2018. 

  • • https://arxiv.org/abs/1609.04626 

Miscellaneous

• (Evolutionary Biology) Vaibhav Mohanty*, Sam F. Greenbury, Tasmin Sarkany, Shyam Narayanan, Kamaludin Dingle, Sebastian E. Ahnert, and Ard A. Louis.  Maximum Mutational Robustness in Genotype-Phenotype Maps Follows a Self-similar Blancmange-like Curve. Journal of the Royal Society Interface.

  • • Press Coverage: 1 (phys.org), 2 (sciencealert.com)

    • https://www.biorxiv.org/content/10.1101/2023.03.11.532236v1

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

  • • https://arxiv.org/abs/2211.03232

• (Scheduling Algorithms) William Kuszmaul and Shyam Narayanan. Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. International Colloquium on Automata, Languages and Programming (ICALP), 2022.

  • • https://arxiv.org/abs/2205.01722

• (Metric Geometry) Josh Alman, Timothy Chu, Gary Miller, Shyam Narayanan, Mark Sellke, and Zhao Song. Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle. In submission.

  • • https://arxiv.org/abs/2011.11503

Undergraduate Thesis (Expository)

• Shyam Narayanan. Modular Forms and Modular Congruences of the Partition Function.

  • • https://www.math.harvard.edu/media/Narayanan-Modular-Forms-Thesis.pdf

*Authors are always listed in alphabetical order, except if authors are starred: then authors are listed in contribution order and starred authors have (equal) first-author contribution.