All homeworks due 5pm on the day listed.

The following courses contain relevant material (from slightly different points of view). Much of the material in this course is inspired by their lectures (although there are many differences as well).

Jelani Nelson's Sketching Algorithms for Big Data at Harvard

Paul Beame's Sublinear (and Streaming) Algorithms at UW

Ilya Razenshteyns's Algorithms Through Geometric Lens at UW

David Woodruff's Algorithms for Big Data at CMU

Greg Valiant's The Modern Algorithmic Toolbox at Stanford

The following books also contain relevant material (and other related topics)

Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman, and Jeff Ullman. [ online copy ]

Foundations of Data Science by Avrim Blum, John Hopcroft, and Ravindran Kannan. [ online copy ]

The goal of the project is to understand a specific problem/area in more depth. This involves reading 1-2 papers thoroughly, and also, trying your hand at improving the results in various ways. We will break the project up into 4 separate milestones:

1) Proposal (due Wed 11/6): submit 1 page proposal on what the project will be about, list the relevant paper(s), and briefly outline what new directions you will explore.

2) Progress (due Mon 11/25): submit 2-3 page summary of the paper(s), based on what you understand so far. Explain the scope of the project and what you hope to find out. List any preliminary results and/or motivating examples and/or fundamental challenges. This progress report should serve (roughly) as the introduction of the final report.

3) Final Presentation (due Mon 12/2 or Wed 12/4): Prepare a 15 minute talk for the class on your project, including the relevant background material, the new results, and any suggestions for future work.

4) Final Report (due Wed 12/11): submit 6-10 page report on the full details of your project. The page limit is loose because it will depend on the format and the number of tables/figures. Ideally, it will look like a first draft of a conference submission (although it's okay if you don't achieve the same number of results as a typical conference paper).

Here is a list of relevant papers. You may choose from this list, or choose paper(s) on your own (as long as they have a geometric/algorithmic component, and they have a significant theoretical component).

Upper and Lower Bounds on the Cost of a Map-Reduce Computation. Foto N. Afrati, Anish Das Sarma, Semih Salihoglu, Jeffrey D. Ullman, VLDB 2013.

Sparser Johnson-Lindenstrauss Transforms Daniel M. Kane, Jelani Nelson, SODA 2012

Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk, Samuel Madden, Pradeep Dubey

Parallel Correlation Clustering on Big Graphs Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, Michael I. Jordan

Hierarchical Clustering for Euclidean Data Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev, AISTATS 2019

CoveringLSH: Locality-Sensitive Hashing without False Negatives. Rasmus Pagh, SODA 2016

Set similarity search beyond MinHash. Tobias Christiani, Rasmus Pagh, STOC 2017

A cost function for similarity-based hierarchical clustering. Sanjoy Dasgupta, SODA 2016 [video]

On Symmetric and Asymmetric LSHs for Inner Product Search Behnam Neyshabur, Nathan Srebro, ICML 2015

Near-Optimal (Euclidean) Metric Compression Piotr Indyk, Tal Wagner, SODA 2017

LSH Forest: Practical Algorithms Made Theoretical Alexandr Andoni,Ilya Razenshteyn, Negev Shekel Nosatzki, SODA 2017

MinJoin: Efficient Edit Similarity Joins via Local Hash Minima Haoyu Zhang, Qin Zhang, KDD 2019

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn, STOC 2019

You may also choose any papers from this other course