Copyright warning: the copyright of each paper belongs to the respective publisher. The local copy is only for non-commercial, personal use.
Fast Optimal Locally Private Mean Estimation via Random Projections
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar.
In Advances in Neural Information Processing Systems 36 (NeurIPS 2023).
Improved Frequency Estimation Algorithms with and without Predictions
Anders Aamand, Justin Y. Chen, Huy Nguyen, Sandeep Silwal, Ali Vakilian.
In Advances in Neural Information Processing Systems 36 (NeurIPS 2023).
Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, Huy Nguyen.
In Advances in Neural Information Processing Systems 36 (NeurIPS 2023).
On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bounded Losses: an Improved Analysis
Ta Duy Nguyen, Alina Ene, Huy Nguyen.
In Advances in Neural Information Processing Systems 36 (NeurIPS 2023).
High Probability Convergence of Stochastic Gradient Methods
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, Huy Le Nguyen
In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Streaming Submodular Maximization with Differential Privacy
Anamay Chaturvedi, Huy Le Nguyen, Thy Nguyen.
In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration
Zijian Liu, Ta Duy Nguyen, Alina Ene, Huy Nguyen.
In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
Improved Learning-augmented Algorithms for k-means and k-medians Clustering
Thy Nguyen, Anamay Chaturvedi, and Huy Nguyen.
In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
Matthew Jones, Huy Nguyen, and Thy Nguyen.
In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), 2023.
Private frequency estimation via projective geometry
Vitaly Feldman, Jelani Nelson, Huy Nguyen, Kunal Talwar.
In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints
Alina Ene, Huy Nguyen.
In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
Zijian Liu, Ta Duy Nguyen, Alina Ene, Huy Nguyen.
In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
Anamay Chaturvedi, Matthew Jones, Huy L. Nguyen.
In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022.
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
Alina Ene, Huy L. Nguyen.
In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022.
Differentially Private Decomposable Submodular Maximization
Anamay Chaturvedi, Huy L. Nguyen, Lydia Zakynthinou.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities
Alina Ene, Huy L. Nguyen, Adrian Vladu.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Differentially Private Clustering via Maximum Coverage
Matthew Jones, Huy L. Nguyen, Thy Nguyen.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Differentially private k-means via exponential mechanism and max cover
Anamay Chaturvedi, Huy L. Nguyen, Eric Xu.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Projection-Free Bandit Optimization with Privacy Guarantees
Alina Ene, Huy L. Nguyen, Adrian Vladu.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Fair k-Centers via Maximum Matching
Matthew Jones, Huy L. Nguyen, Thy Nguyen.
In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Parallel Algorithm for Non-Monotone DR-Submodular Maximization
Alina Ene, Huy L. Nguyen.
In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh.
In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), 2020.
Efficient Private Algorithms for Learning Halfspaces
Huy L. Nguyen, Jonathan Ullman, and Lydia Zakynthinou.
In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT), 2020.
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
Alina Ene, Huy L. Nguyen.
In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019.
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Alina Ene, Huy L. Nguyen.
In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019.
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, and Adrian Vladu.
In Proceedings of the 51st Annual Symposium on the Theory of
Computing (STOC), 2019.
Fast greedy for linear matroids
Huy L. Nguyen.
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
Alina Ene, Huy L. Nguyen.
In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
Improved Algorithms for Collaborative PAC Learning
Huy L. Nguyen, Lydia Zakynthinou.
In Advances in Neural Information Processing Systems 31 (NeurIPS 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
Alina Ene, Huy L. Nguyen.
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]