CS369G: Project
Spring Quarter 2016, Stanford University
The course has a project requirement that constitutes 30% of the final grade.
The project is due Wed June 8 1:29pm.
To claim a particular paper to write a report about send an email to the staff list listing your team. To check whether a paper has been picked check this document.
Goal
The purpose of the project is to get you acquainted with recent developments related to the topics discussed in class. Students will pick a research paper from a list of possible topics and write a report about. Focusing on one paper will allow you to go into depth in a particular problem and thus see how the various ideas you have seen in the course can be applied or extended. The course project is a nice starting point for further research investigation and possibly an original contribution.
Guidelines
Students should form teams of two people and pick a paper to write a report about. If you want to pick a paper that is not on the list, you should email the staff list with a brief explanation of how it relates to the topics of the class. Also, after request we may allow a project submission by a single person. To check whether a paper has been picked check this document.
Scope: a succesful project is one that indicates that you have understood in depth the main ideas and techniques employed in the paper. You should not present all the details of the paper, but only include enough detail so that the main steps are clear and well motivated. The report should put emphasis on clarity and try to convert the intuition. The level of exposition should be suitable for a graduate student that is taking this class. To get an idea of the size of the report think of it as supporting notes for a twohour lecture (around 10 pages).
Project Topics
Hashing
Fast CrossPolytope LocalitySensitive Hashing, Kennedy, R. Ward, 2016.
Practical and Optimal LSH for Angular Distance, A. Andoni et al., NIPS 2015.
Optimal DataDependent Hashing for Approximate Near Neighbors, Andoni, Razenshteyn, STOC 2015.
Hashing for statistics over kpartitions, Dahlgaard et al., FOCS 2015.
Sketching  Sparsification
On Fully Dynamic Graph Sparsifiers I. Abraham et al., 2016.
An Optimal Algorithm for ℓ1Heavy Hitters in Insertion Streams and Related Problems, A. Bhattacharyya et al., PODS 2016
Graphical Model Sketch, Kveton et al., 2016.
Heavy hitters via clusterpreserving clustering, K.G. Larsen et al., 2016.
BPTree: an ℓ2 heavy hitters algorithm using constant memory, V. Braverman etl., 2016.
Beating CountSketch for Heavy Hitters in Insertion Streams, V. Braverman et al., STOC 2016.
Sparsification of TwoVariable Valued CSPs, Filtser, Krauthgamer, 2015
Lp Row Sampling by Lewis Weights, M.B. Cohen, R. Peng, STOC 2015.
A Unified Approach for Clustering Problems on Sliding Windows, V. Braverman et al., 2015.
Sketching for Mestimators: a unified approach to robust regression, K.L. Clarkson, D.P. Woodruff, SODA 2015.
Single Pass Spectral Sparsification in Dynamic Streams, M. Kapralov et al., FOCS 2014.
Towards (1 + ε)approximate flow sparsifiers, Andoni, Gupta, Krauthgamer, SODA 2014.
Counting Arbitrary Subgraphs in Data Streams, D.M. Kane et al., ICALP 2012
Dimensionality Reduction
Universality Laws for Randomized Reduction with Applications, S Oymak, J.A. Tropp, 2015.
NearOptimal Bounds for Binary Embeddings of Arbitrary Sets, S Oymak, B. Recht, 2015.
Isometric sketching of any set via the Restricted Isometry Property, S. Oymak et al, 2015.
Dimensionality Reduction for kMeans Clustering and Low Rank Approximation, M. B. Cohen et al., STOC 2015.
Towards a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space, J Bourgain et al, STOC 2015
Spectral Approaches to Nearest Neighbor Search, Abdullah et al., FOCS 2014.
Sparser JohnsonLindenstrauss Transforms, Daniel M. Kane, Jelani Nelson, SODA 2012.
Fast Numerical Linear Algebra
Approximate Gaussian Elimination for Laplacians, R. Kyng, S. Sachdeva, 2016
Streaming PCA: Matching Matrix Bernstein and NearOptimal Finite Sample Guarantees for Oja's Algorithm, P. Jain et al, 2016.
Optimal Principal Component Analysis in Distributed and Streaming Models, C. Boutsidis et al., STOC 2016.
Weighted Low Rank Approximations with Provable Guarantees, I. Razenshteyn et al., STOC 2016.
Nearly tight oblivious subspace embeddings by trace inequalities, M.B. Cohen, SODA 2016.
Optimal approximate matrix product in terms of stable rank, M.B. Cohen et al., 2015.
Optimal CUR matrix decompositions, Christos Boutsidis, David P. Woodruff, STOC 2014.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, Jelani Nelson, Huy L. Nguyen, FOCS 2013
