Thuy-Duong "June" Vuong



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

I am a 4th year PhD student in the Computer Science Theory Group at Stanford University advised by Nima Anari and Moses Charikar. I use the geometry of polynomials and theory of high dimensional expanders in designing sampling, counting and optimization algorithms, particularly in the analysis of Markov chains.
I did my undergraduate at the Massachusetts Institute of Technology (MIT), in Mathematics and Computer Science.
My research is supported by a Microsoft Research PhD Fellowship.

Publications and Preprints

Counting, sampling, and Markov chains

  1. Parallel Discrete Sampling via Continuous Walks, joint with Nima Anari, Yizhi Huang, Tianyu Liu, Brian Xu and Katherine Yu. To appear in the 55th ACM Symposium on the Theory of Computing (STOC 2023).
  2. Quadratic Speedups in Parallel Sampling from Determinantal Distributions, joint with Nima Anari, Callum Burgess and Kevin Tian. To appear in SPAA 2023.
  3. 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 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022). [arXiv:2102.05347v3]. Slides.
  4. On the Complexity of Sampling Redistricting Plans, joint with Moses Charikar , Paul Liu and Tianyu Liu. [arXiv:2206.04883]. Slides.
  5. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain, joint with Vishesh Jain and Huy Tuan Pham. Submitted. [arXiv:2203.03858]
  6. 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]
  7. 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.
  8. Spectral independence, coupling, and the spectral gap of the Glauber dynamics, joint with Vishesh Jain and Huy Tuan Pham. To appear in Information Processing Letters. [arXiv:2105.01201]
  9. Domain Sparsification of Discrete Distributions using Entropic Independence, joint with Nima Anari, Michał Dereziński, and Elizabeth Yang. Appear in 14th Innovations in Theoretical Computer Science (ITCS 2022). [arXiv:2102.05347v3]. Slides.
  10. On the sampling Lovász Local Lemma for atomic constraint satisfaction problems, joint with Vishesh Jain and Huy Tuan Pham. Submitted. [arXiv:2102.08342]
  11. Towards the sampling Lovász Local Lemma, joint with Vishesh Jain and Huy Tuan Pham. Appear in 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021). [arXiv:2011.12196].
  12. 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.
  13. 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 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. Reviewer for STOC23, SODA23, RANDOM22.
  2. Mentoring: Stanford Women in Math Mentoring (SWIMM)
  3. Teaching Assistantships: CS 161 Winter 2022, CS 263 Autumn 2020.