Papers for projects Please do projects in groups of size 2. You can choose a paper by claiming it on the piazza thread. On Dec 3, we will have presentations in class (10 mins per group), saying something that will be interesting and educational for your classmates (and me). You have to do a writeup of 10 pages, giving an overview of the paper, and including 1 detailed proof of some interesting statement central to the paper. This writeup can be submitted upto by Dec 20. You can also ask to do a different paper if it is sufficiently related to the themes of the course -- please email me if you want to do this. Expander Random Walks: A Fourier-Analytic Approach https://www.cs.tau.ac.il/~amnon/Papers/CPT.stoc21.pdf On the second eigenvalue of random regular graphs https://dl.acm.org/doi/pdf/10.1145/73007.73063 Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries https://drops.dagstuhl.de/storage/00lipics/lipics-vol300-ccc2024/LIPIcs.CCC.2024.8/LIPIcs.CCC.2024.8.pdf An Elementary Construction of Constant-Degree Expanders https://web.math.princeton.edu/~nalon/PDFS/expander7.pdf EXPLICIT GRAPHS WITH EXTENSION PROPERTIES https://dept.math.lsa.umich.edu/~ablass/k-extension.pdf Derandomized Squaring of Graphs https://people.seas.harvard.edu/~salil/research/derand_squaring.pdf Randomness-Efficient Sampling within NC1 https://link.springer.com/article/10.1007/s00037-007-0238-5 LIFTS, DISCREPANCY AND NEARLY OPTIMAL SPECTRAL GAP https://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf Eigenvalues and Expansion of Regular Graphs https://www.cs.princeton.edu/~zdvir/expanders/Kahale.pdf Cutoff on all Ramanujan graphs https://link.springer.com/article/10.1007/s00039-016-0382-7 Explicit constructions of linear-sized superconcentrators https://www.sciencedirect.com/science/article/pii/0022000081900404 Non-backtracking random walks mix faster https://arxiv.org/abs/math/0610550 Asymptotically optimal induced universal graphs https://web.math.princeton.edu/~nalon/PDFS/induniv5.pdf Sparse Universal Graphs for Bounded-Degree Graphs https://web.math.princeton.edu/~nalon/PDFS/ugnew4.pdf