[Colloquium] CS Seminar - Nguyen Thuy Duong Vuong April 18, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO

COMPUTER SCIENCE DEPARTMENT

PRESENTS



Nguyen Thuy Duong Vuong
Stanford University


 [cid:image001.jpg at 01D85008.3F3D92F0]

Tuesday, April 18, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107

Title: “From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization”


 Abstract: "We show a connection between sampling and optimization on discrete domains. For a family of distributions mu defined on size k subsets of a ground set of elements that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find max mu( . )$. More precisely we show that if t-step down-up random walks have spectral gap at least inverse polynomially large, then $t$-step local search can find max mu( . ) within a factor of k^{O(k)}. As the main application of our result, we show that 2-step local search achieves a nearly-optimal k^{O(k)}-factor approximation for MAP inference on nonsymmetric k-DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem.

We establish the connection between sampling and optimization by showing that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks."

Based on joint work with Nima Anari.

Bio: NguyenThuy-Duong "June" Vuong is a third year PhD student at Stanford University, working with Nima Anari and Moses Charikar. She works on geometry of polynomials, with applications in sampling and optimization algorithms over combinatorial domain.



Host: Madhur Tulsiani





--
Jose J Fragoso
Project Assistant IV
Computer Science Department
5730 S. Ellis – Room 200C
Chicago, IL. 60637
jfragoso at uchicago.edu
(773) 702-6614
(773) 702-8487 FAX

[signature_1572818061]



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220414/136ec39a/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 36349 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220414/136ec39a/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 459508 bytes
Desc: image003.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220414/136ec39a/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: JuneVuongFlier.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 54489 bytes
Desc: JuneVuongFlier.docx
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220414/136ec39a/attachment-0001.docx>