Huy Lê Nguyễn

my photo

I am a research assistant professor at TTIC. My main research interests are algorithms for massive data (or in more fashionable language, "big data").

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 (university name) dot edu

Program committees: FOCS 2015, MASSIVE 2015.

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

Publications

2015

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]

2014

On Communication Cost of Distributed Statistical Estimation and Dimensionality (with Ankit Garg and Tengyu Ma). In Proceedings of 28th Annual Conference on Neural Information Processing Systems (NIPS), 2014. Oral presentation.

Subspace Embeddings for the Polynomial Kernel (with Haim Avron and David P. Woodruff). In Proceedings of 28th Annual Conference on Neural Information Processing Systems (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.

2013

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.

2012

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.

2011

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.

2010

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]

2009

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]

Manuscripts

Approximate Nearest Neighbor Search in p. 2013. [arXiv]

Miscellanea

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.