# Final project reading list for Randomized algorithms
###### tags: `Randomized Algorithms`
###### 2024 Spring

> You can select one of the papers in the following list for the final project. For each listed paper, the notation 'n*' indicates that you may form a group of 'n' persons to study teh paper and write up the final report.
> The format and guideline of yuor report should include:
> 1. A brief introduction of the motivation.
> 2. The precise defintion of the problem and the main result(s).
> 3. Outline the proof idea of the main result.
> 4. Using examples and figure can help explain the idea. For example, some of the constructive results can be well explained with proper examples.
> 5. The writing should be clear and understandable by non-experts.
>

# Paper list:
1. [2* Facility Location in the Sublinear Geometric Model, Morteza Monemizadeh, APPROX/RANDOM 2023](https://drops.dagstuhl.de/storage/00lipics/lipics-vol275-approx-random2023/LIPIcs.APPROX-RANDOM.2023.6/LIPIcs.APPROX-RANDOM.2023.6.pdf)
2. [2* On the correlation of parity and small-depth circuits, J Håstad, SIAM Journal on Computing, 2014](https://epubs.siam.org/doi/pdf/10.1137/120897432)
3. [1* Depth two majority circuits for majority and list expanders, K Amano - Mathematical Foundations of Computer Science, 2018](https://drops.dagstuhl.de/storage/00lipics/lipics-vol117-mfcs2018/LIPIcs.MFCS.2018.81/LIPIcs.MFCS.2018.81.pdf)
4. [2* Explicit construction of a small epsilon-net for linear threshold functions, Y Rabani, A Shpilka, SIAM Journal on Computing, 2010, Corrigendum 2022](https://www.cs.tau.ac.il/~shpilka/publications/RabaniShpilka09.pdf)
5. [1* On the sample complexity of privately learning axis-aligned rectangles, M Sadigurschi, U Stemmer, Advances in Neural Information Processing Systems, 2021](https://proceedings.neurips.cc/paper_files/paper/2021/file/ee0e95249268b86ff2053bef214bfeda-Paper.pdf)
6. [2* Pseudorandomness via the discrete fourier transform, P Gopalan, DM Kane, R Meka, SIAM Journal on Computing, 2018](https://epubs.siam.org/doi/pdf/10.1137/16M1062132)
7. [2* Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy, David Rasmussen, Lolck Rasmus Pagh - SODA 2024](https://epubs.siam.org/doi/epdf/10.1137/1.9781611977912.40)
8. [2* Explicit expanders of every degree and size, N Alon](https://link.springer.com/content/pdf/10.1007/s00493-020-4429-x.pdf)
9. [1* New explicit constant-degree lossless expanders, L Golowich, 2024 SODA](https://arxiv.org/abs/2306.07551)
10. [2* Bipartite unique-neighbour expanders via Ramanujan graphs, R Asherov, I Dinur](https://arxiv.org/abs/2301.03072)
11. [2* Satisfiability coding lemma, R Paturi, P Pudlák, F Zane, Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, 1997](https://mathweb.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/paturi97satisfiability.pdf)
12.