Suggested papers for the project:
1. Sublinear algorithms for graphs
Converting online algorithms to local computation algorithms Mansour, Rubinstein, Vardi, Xie
Space-efficient local computation algorithms Alon, Rubinfeld, Vardi, Xie
2. Error-correcting codes
Linear-time decoding of regular expander codes Viderman.
New affine-invariant codes from lifting Guo, Sudan.
On the locality of codeword symbols Gopalan, Huan, Simitci, Yekhanin.
Dense locally-testable codes cannot have constant rate and distance Dinur, Kaufman.
Expander-based constructions of efficiently decodable codes Guruswami, Indyk.
Matching vectors codes Dvir, Gopalan, Yekhanin.
3. Comunication complexity (and property testing, additive combinatorics)
Property testing lower bounds via communication complexity Blais, Brody, Matulef.
An additive combinatorics approach relating rank to communication complexity Ben-Sasson, Lovett, Ron-Zewi.
Analyzing graph structure via linear measurements Ahn, Guha, McGregor.
Graph sketches: sparsifications, spanners and subgraphs Ahn, Guha, McGregor.
An optimal algorithm for the Distincts elements problem Kane, Nelson, Woodruff.
Counting triangles in graph streams Buriol,Frahling, Leonardi, Spaccamela, Sohler.
Approximating the longest increasing sequence Gopalan, Jayram, Krauthgamer, Kumar
Testing basic boolean formulae Parnas, Ron, Samorodnitsky
Nearly complete graphs decomposable into large induced matchings Alon, Moitra, Sudakov
On Sunflowers and Matrix Multiplication, Alon, Shpilka, Umans
Are bit vectors optimal? Buhrman, Miltersen, Radhkrishnan, Venkatesh
Subspace-evasive sets Dvir, Lovett
Testing and reconstruction of Lipschitz functions with applications to data privacy Jha, Raskhodnikova