I am an assistant professor at Northeastern University. Before coming here, I spent a year at the Toyota Technological Institute at Chicago and a year at the Simons Institute at UC Berkeley. My main research interests are algorithms for massive data (or in more fashionable language, "big data").

I got my Ph.D. in computer science from Princeton. I was very fortunate to have Prof. Moses Charikar as my advisor. Before coming to Princeton, I studied computer science and math (courses 6 and 18) at MIT.

The best way to reach me is via email at hlnguyen at cs dot princeton dot edu

CS7800: Advanced Algorithms. Fall '18.

CS4800: Algorithms and Data. Spring '18, Spring '17, Fall '16.

Copyright warning: the copyright of each paper belongs to the respective publisher. The local copy is only for non-commercial, personal use.

Fast greedy for linear matroids. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time (with Alina Ene). In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

Improved Algorithms for Collaborative PAC Learning (with Lydia Zakynthinou). In Advances in Neural Information Processing Systems 31 (NIPS 2018).

Decomposable Submodular Function Minimization: Discrete and Continuous (with Alina Ene and László A. Végh). In Advances in Neural Information Processing Systems 30 (NIPS 2017).

Approximate near neighbors for general symmetric norms (with Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten). In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC), 2017.

Heavy hitters via cluster-preserving clustering (with Kasper Green Larsen, Jelani Nelson, and Mikkel Thorup). In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016. [arXiv]

Constrained Submodular Maximization: Beyond 1/e (with Alina Ene). In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016. [arXiv]

A New Framework for Distributed Submodular Maximization (with Rafael da Ponte Barbosa, Alina Ene, and Justin Ward). In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016. [arXiv]

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality (with Mark Braverman, Ankit Garg, Tengyu Ma, and David P. Woodruff). In Proceedings of the 48th Annual Symposium on the Theory of Computing (STOC), 2016. [arXiv]

A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns (with Alina Ene). 2016

Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions (with Alina Ene). In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015. [arXiv]

The Power of Randomization: Distributed Submodular Maximization on Massive Datasets (with Rafael Barbosa, Alina Ene, and Justin Ward). In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015. [arXiv]

Approximate k-flat Nearest Neighbor Search (with Wolfgang Mulzer, Paul Seiferth, and Yannik Stein). In Proceedings of the 47th Annual Symposium on the Theory of Computing (STOC), 2015. [arXiv]

Time lower bounds for nonadaptive turnstile streaming algorithms (with Kasper Green Larsen and Jelani Nelson). In Proceedings of the 47th Annual Symposium on the Theory of Computing (STOC), 2015. [arXiv]

On Communication Cost of Distributed Statistical Estimation and Dimensionality (with Ankit Garg and Tengyu Ma). In Advances in Neural Information Processing Systems 27 (NIPS 2014). Oral presentation.

Subspace Embeddings for the Polynomial Kernel (with Haim Avron and David P. Woodruff). In Advances in Neural Information Processing Systems 27 (NIPS 2014).

From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route? (with Alina Ene). In Proceedings of the 22nd European Symposium on Algorithms (ESA), 2014.

Online Bipartite Matching with Decomposable Weights (with Moses Charikar and Monika Henzinger). In Proceedings of the 22nd European Symposium on Algorithms (ESA), 2014.

Lower bounds for oblivious subspace embeddings (with Jelani Nelson). In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014. [arXiv]

Turnstile Streaming Algorithms Might as Well Be Linear Sketches (with Yi Li and David P. Woodruff). In Proceedings of the 46th Annual Symposium on the Theory of Computing (STOC), 2014.

Preserving Terminal Distances using Minors (with Robert Krauthgamer and Tamar Zondiner). SIAM Journal on Discrete Mathematics 28(1), 127-141, 2014. Preliminary version by my co-authors appeared in ICALP 2012.

Beyond Locality-Sensitive Hashing (with Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn). In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. [arXiv]

Cutting corners cheaply, or how to remove Steiner points (with Lior Kamma and Robert Krauthgamer). In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. [arXiv]

On Sketching Matrix Norms and the Top Singular Vector (with Yi Li and David P. Woodruff). In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings (with Jelani Nelson). In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013. [arXiv]

Tight Lower Bound for Linear Sketches of Moments (with Alexandr Andoni, Yury Polyanskiy, and Yihong Wu). In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), 2013.

Sparsity lower bounds for dimensionality reducing maps (with Jelani Nelson). In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), 2013. [arXiv]

On the Convergence of the Hegselmann–Krause System (with Arnab Bhattacharyya, Mark Braverman, and Bernard Chazelle). In Proceedings of the 4th Innovations in Theoretical Computer Science (ITCS) conference, 2013. [arXiv]

Eigenvalues of a matrix in the streaming model (with Alexandr Andoni). In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.

Approximate Nearest Neighbor Search in
*ℓ _{p}*. 2013. [arXiv]

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation (with Jelani Nelson and David P. Woodruff). Linear Algebra and its Applications. Special Issue on Sparse Approximate Solution of Linear Systems, 441: 152-167, January 15, 2014. Preliminary version appeared in RANDOM, 2012. [arXiv]

Improved Range Searching Lower Bounds (with Kasper Green Larsen). In Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG), 2012. [ACM] [pdf]

Width of Points in the Streaming Model (with Alexandr Andoni). Accepted to Transactions on Algorithms special issue on SODA '12. Preliminary version in SODA '12.

Near Linear Lower Bounds for Dimension Reduction in L1 (with Alexandr Andoni, Moses Charikar, and Ofer Neiman). In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011.

Sublinear Time Algorithms for Earth Mover's Distance (with Khanh Do Ba, Huy N. Nguyen, and Ronitt Rubinfeld). In Theory of Computing Systems. Volume 48, Number 2, 428-442. 2011.

Near-Optimal Sublinear Time Algorithms for Ulam Distance (with Alexandr Andoni). In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. [pdf] [ps]

Approximate Line Nearest Neighbor in High Dimensions (with Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer). In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009. [pdf] [ps]

Program committees: AISTATS 2017, ICML 2016, COCOON 2016, FOCS 2015, MASSIVE 2015.

I was a guest co-editor of ACM XRDS issue on "Big Data". Check out the issue's overview article (written with Andrew Cron and Aditya Parameswaran).

MIT campus map that I helped develop.

The proper spelling of my name in Vietnamese order is Nguyễn Lê Huy.