Under construction...

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.

    • 4. Streaming

  • 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

    • 5. Miscelaneous

  • 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