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.
Stashed changes