Thuy-Duong "June" Vuong



CS Theory Group, Stanford University
Office: Gates 198
Email:   tdvuong at stanford dot edu
Links: CV, Google Scholar

I am a final year PhD student in the Computer Science Theory Group at Stanford University advised by Nima Anari and Moses Charikar. My research is in designing and analyzing algorithms for sampling from high-dimensional complex distributions. I am supported by a Microsoft Research PhD Fellowship.
I received my Bachelor's degrees in Mathematics and Computer Science at the Massachusetts Institute of Technology (MIT) in 2019.
I am on the job market for tenure-track positions.

Publications and Preprints

Counting, sampling, and Markov chains

  1. Trickle-Down in Localization Schemes and Applications, joint with Nima Anari and Frederic Koehler. To appear in the 56th ACM Symposium on the Theory of Computing (STOC 2024).
  2. Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization, joint with Frederic Koehler. To appear in the International Conference on Learning Representations (ICLR 2024). [arXiv:2310.01762]
  3. Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses, joint with Nima Anari, Vishesh Jain , Frederic Koehler, and Huy Tuan Pham. Appear in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2024). [arXiv:2307.10466]
  4. Optimal mixing of the down-up walk on independent sets of a given size, joint with Vishesh Jain , Marcus Michelen, and Huy Tuan Pham. Appear in the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023). [arXiv:2305.06198]
  5. Parallel Discrete Sampling via Continuous Walks, joint with Nima Anari, Yizhi Huang, Tianyu Liu, Brian Xu and Katherine Yu. Appear in the 55th ACM Symposium on the Theory of Computing (STOC 2023).
  6. Quadratic Speedups in Parallel Sampling from Determinantal Distributions, joint with Nima Anari, Callum Burgess and Kevin Tian. Appear in the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2023).
  7. Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence, joint with Nima Anari and Yang P. Liu. Appear in the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022). [arXiv:2102.05347v3]. Slides.
  8. On the Complexity of Sampling Redistricting Plans, joint with Moses Charikar , Paul Liu and Tianyu Liu. [arXiv:2206.04883]. Slides.
  9. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain, joint with Vishesh Jain and Huy Tuan Pham. Submitted. [arXiv:2203.03858]
  10. Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities, joint with Nima Anari, Vishesh Jain , Frederic Koehler, and Huy Tuan Pham. Appear in the 54th ACM Symposium on the Theory of Computing (STOC 2022) as a merge with Entropic Independence I. [arXiv:2111.03247]
  11. Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models, joint with Nima Anari, Vishesh Jain , Frederic Koehler, and Huy Tuan Pham. Appear in the 54th ACM Symposium on the Theory of Computing (STOC 2022). [arXiv:2106.04105]. Slides. Video.
  12. Spectral independence, coupling, and the spectral gap of the Glauber dynamics, joint with Vishesh Jain and Huy Tuan Pham. Appear in Information Processing Letters. [arXiv:2105.01201]
  13. Domain Sparsification of Discrete Distributions using Entropic Independence, joint with Nima Anari, Michał Dereziński, and Elizabeth Yang. Appear in the 14th Innovations in Theoretical Computer Science (ITCS 2022). [arXiv:2102.05347v3]. Slides.
  14. On the sampling Lovász Local Lemma for atomic constraint satisfaction problems, joint with Vishesh Jain and Huy Tuan Pham. Submitted. [arXiv:2102.08342]
  15. Towards the sampling Lovász Local Lemma, joint with Vishesh Jain and Huy Tuan Pham. Appear in the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021). [arXiv:2011.12196].
  16. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more, joint with Yeganeh Alimohammadi, Nima Anari, and Kirankumar Shiragur. Appear in the 53rd ACM Symposium on the Theory of Computing (STOC 2021). [arXiv:2102.02708v2]. Slides. Video.
  17. Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests, joint with Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant. Appear in the 53rd ACM Symposium on the Theory of Computing (STOC 2021). [arXiv:2004.07220]. Slides.

Optimization

  1. Composable Coresets for Constrained Determinant Maximization and Beyond, joint with Sepideh Mahabadi . [arXiv:2211.00289]
  2. From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization, joint with Nima Anari. Appear in 35th Conference on Learning Theory (COLT 2022). [arXiv:2102.05347v3]. Slides.
  3. An Extension of Plucker Relations with Applications to Subdeterminant Maximization, joint with Nima Anari. Appear in the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020). [arXiv:2004.13018]. Slides.
During my undergraduate studies, I had the pleasure of doing research with Virginia Vassilevska Williams and Vinod Vaikuntanathan at MIT, and with students and mentors at the REU at University of Minnesota, Twin Cities. These projects have resulted in the following papers.

Undergraduate projects

  1. Lattice trapdoors and IBE from middle-product LWE, joint with Alex Lombardi and Vinod Vaikuntanathan. Appear in Theory of Cryptography Conference (TCC19). [ePrint:2019/1067]
  2. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles, joint with Mina Dalirrooyfard and Virginia V. Williams. Appear in the 51st ACM Symposium on the Theory of Computing (STOC 2019) and accepted to SIAM Journal on Computing, Volume 50. [arXiv:1904.03741]
  3. Toric Mutations in the dP2 Quiver and Subgraphs of the dP2 Brane Tiling, joint with Yibo Gao, Zhaoqi Li and Lisa Yang. Appear in the Electronic Journal of Combinatorics. [arXiv:1611.05320]

Talks/Slides/Videos

  1. Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence. Slides. Talks given at
    • University of Illinois Chicago (UIC)'s CS Theory Seminar
    • Toyota Technological Institute at Chicago (TTIC) Young Researcher Seminar Series
  2. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. Slides. Video. Talks given at
    • Northwestern Theory Seminar
    • Google Research Mountain View
    • University of Washington (UW) Theory Seminar
  3. Entropic independence: optimal mixing of down-up random walks. Slides. Video. Talks given at
    • University of Chicago Combinatorics Seminar
    • ETH Zurich Algorithm & Complexity Seminar
    • UC Santa Barbara (UCSB) Theory Seminar
  4. From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization. Slides. Talk given at University of Illinois Chicago's Combinatorics Seminar.
  5. On the Complexity of Sampling Redistricting Plans. Slides. Talk given at Tufts University (informal, virtual) seminar.

Services

  1. Journal reviewer: SIAM Journal on Computing (SICOMP), Transactions on Algorithms (TALG)
  2. Conference reviewer: STOC 24, NeurIPS23, STOC23, SODA23, RANDOM22.
  3. Mentoring: Stanford Women in Math Mentoring (SWIMM), CURIS, LINXS.

Teaching

  1. Design and Analysis of Algorithms (CS 161), Winter 2022
  2. Counting and Sampling (CS 263), Autumn 2020