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
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).
Quadratic Speedups in Parallel Sampling from Determinantal Distributions, joint with Nima Anari, Callum Burgess and Kevin Tian. To appear in SPAA 2023.
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.
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]
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]
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].
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.
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.
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]
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
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
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
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
From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization. Slides. Talk given at University of Illinois Chicago's Combinatorics Seminar.
On the Complexity of Sampling Redistricting Plans. Slides. Talk given at Tufts University (informal, virtual) seminar.