The project is intentionally left open ended and you should try to make it more exciting for yourself. You are supposed to choose a theory paper (appeared in any of the theory conferences, e.g., FOCS, STOC, SODA, ICALP, ITCS, PODC, etc). The paper is supposed to be relatively recent, say it is to be published not earlier than 2000.
You can do the project in groups of at most 2 students
Please send me the paper that you would like to work on together with your group by Monday Nov 16th.

Option 1: Write a summary of the paper. Your summary should contain the following items:

• Introduction: This part should contain the problem definition, motivations, applications, and the previous works.
• Main contributions: This part should contain the main results of the paper, the algorithm and the implications of the results.
• Overview of the proof: In this part you should give a high-level overview of the proof and the main ideas. What is the novelty of the paper which makes it different from the previous work?
• Details of the proof: In this part you should write your understanding of the proof. For example you can provide several examples for elaboration purposes. You can also try to go over the main steps and the main lemmas of the proof. Try to understand the proof as best as you can.
• You cannot copy-paste lemmas/proofs from the paper.

Option 2: For this option you should do an empirical study of the paper. In most theory papers typically there is no empirical evaluation. In this case you are supposed to implement the algorithm proposed in the paper and run it against some test cases. You may generate your own test cases or you may use actual data from real world applications. It would be ideal if you compare the performance of the algorithm with a ``greedy'' algorithm or any reasonable algorithm that come to your mind. Please write a report describing the algorithm proposed in the paper, a description of your proposed algorithm and the details of your findings. Please also send in your code and your test data.

Option 3: In this case you are supposed to relate the paper to your own field of interest. For example, you may modify the algorithm suggested in the paper and add a heuristic on top of it and run it against a real world problem in your field of study. In your report please describe the algorithm in the paper and say your modifications. Then, go over the problem in your area that you are trying to solve. Then, describe the test data and the performance of your proposed solution for those test cases. Theoretical justifications for your proposed solution would make this a great project.