List of papers

Once you decide to take the course for credit, send an e-mail to me (parinya.chalermsook@aalto.fi)  

Each student must select one paper. Once a paper is selected, you would be assigned a *supervisor* (either a professor or a postdoc) who could provide you guidelines on how to read the paper, write the report, and prepare a presentation. Your grades will be a linear combination of (i) the quality of your presentation, (ii) the depth of your understanding on the topic, and (iii) the quality of the final report. The precise linear combination factors will be determined later. 

Here is a list of papers groupped by the supervisors & their contact information. Students are encouraged to get in touch with their supervisors as soon as the paper's choice is fixed. 



Alkida Balliu

Local Checkability, No Strings Attached
[reservedFeedback from nature: an optimal distributed algorithm for maximal independent set selection


Chris Brzuska

1. Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan: Average-case fine-grained hardness. STOC 2017: 483-496
https://doi.org/10.1145/3055399.3055466

2. Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan: Proofs of useful work. IACR Cryptology ePrint Archive 2017: 203 (2017)
https://eprint.iacr.org/2017/203

3. Cody Murray, Ryan Williams: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, ECCC Report TR17-188, 23 December 2017.
https://eccc.weizmann.ac.il/report/2017/188/


Parinya Chalermsook

  • [reserved] Uriel Feige. Approximating Maximum Clique by Removing Subgraphs. 
  • Anna Adamaszek, Sariel Har-Peled, Andreas Wiese. Approximation Schemes for Independent Set and Sparse Subset of Polygons. 


Aris Gionis


1. [reserved] Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal. Deterministic and probabilistic binary search in graphs. In Proceedings of STOC 2016

2. [reserved] Andrew Guillory, Jeff Bilmes. Label Selection on Graphs. In Advances in Neural Information Processing Systems (NIPS) 2009

3. [reserved] David Bindel, Jon M. Kleinberg, Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior 92: 248-265 (2015)

Petteri Kaski

1. Josh Alman, Virginia Vassilevska Williams: Further limitations of the known approaches for matrix multiplication, arXiv:1712.07246, 21 December 2017.
https://arxiv.org/abs/1712.07246

2. Jianyu Huang, Leslie Rice, Devin A. Matthews, Robert A. van de Geijn: Generating Families of Practical Fast Matrix Multiplication Algorithms, 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS).
https://doi.org/10.1109/IPDPS.2017.56

3. Cody Murray, Ryan Williams: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, ECCC Report TR17-188, 23 December 2017.
https://eccc.weizmann.ac.il/report/2017/188/


Dennis Olivetti

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
[reservedA Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities


Mikaël Rabie



Last modified: Wednesday, 7 February 2018, 11:22 AM