For the course project, the goal will be for individuals and teams to read some recent research papers, and either do (a) a survey of the related work on a problem:
(b) do the above, with less of an emphasis on summarizing the most relevant work and more focus on working through some possible techniques for solving some open problems
(c) propose a new algorithmic problem
We’re looking for a 5-10 page writeup, presumably on the longer end if doing work in a pair, and a 10-20 minute presentation. We’ll talk more about these details once people pick groups and projects.
I would like for everyone to do this project either in pairs or individually; please use Piazza to help find a partner if you don’t have one. When you have a partner, or have decided to work individually, please fill in this google form.
with a brief summary
of what you’d like to do your project on.
Here’s a list of a few topics that whoever emails us first is welcome to present upon. Feel free to invent your own, these are just a few ideas to get you going.
We briefly talked about the complexity of min-sum products. There are some interesting [average-case results] (https://www.sciencedirect.com/science/article/pii/S0304397515008105). Describe some of the (recent) average-case results. What makes this problem substantially easier than the worst case? What are some other useful applications (besides finding short paths) of using min-sum products?
Pick one of the recent accepted STOC papers or SODA papers and present the main ideas/breakthroughs in the paper as compared to prior work on the algorithmic problem.
Fair and Diverse sampling, based on this paper. One would need to learn background on DPP, k-DPP.
On the algorithmic side of sampling of the previous paper, they can just focus on this work. It’s MCMC technique + log submodular concepts in there.
If someone likes more statistical side of diversity sampling (for statistical efficiency): https://arxiv.org/abs/1710.05110 . The algorithmic focus there is a pretty nice exercise (not too hard) to grasp too.
MW update is used for differential privacy: private MW or the more ambitious generalization.
If you have some idea of an area you’re interested in, please meet with Tao or Jamie to discuss if you need some pointers.