CS7880: Special Topics in Theoretical Computer Science

Course Staff

Huy L. Nguyen (WVH 358)

Office hour: Thursday 1:25 - 2:25pm

Class Time: Monday & Thursday 11:45 am – 1:25 pm

Class Room: Ryder Hall 296

Discussion Forum: Piazza

Overview

this course will discuss various algorithmic paradigms for efficiently processing large datasets. We will cover streaming and sketching algorithms that produce compact representations of the data, dimension reduction methods that preserve geometric structure, and efficient algorithms for numerical linear algebra.

Grading

Students are expected to solve problem sets (20%), scribe a lecture and help grade a problem set (10%), present a research paper (10%), and complete a research project (60%).

Homework 1 and Latex source

Paper presentation

• Optimal terminal dimensionality reduction in Euclidean space
• Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
• Perfect L_p Sampling in a Data Stream(long paper)
• Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
• On Fully Dynamic Graph Sparsifiers (long paper)

LaTeX

You should prepare your homework solutions using LaTeX. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. Great editors exist on most platforms. Some recomend TexShop for Mac. TeXstudio is a good cross-platform editor.

The not so short introduction to Latex is a good reference to get you started.