Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] course announcement: Algorithmic Techniques for Big Data

Moses Charikar moses at
Mon Mar 28 08:26:36 PDT 2022

Dear theory friends,

If you would like to learn cool theory tools for big data, you might be
interested in the course I'm teaching this quarter (details below).


PS  Apologies if you got duplicate copies of this course announcement

CS 368: Algorithmic Techniques for Big Data
Instructor: Moses Charikar

Spring 2022
Mon-Wed 9:45-11:15
Mitchell Earth Sciences B67


Designing algorithms for efficient processing of large data sets poses
unique challenges. This course will discuss algorithmic paradigms that have
been developed to efficiently process data sets that are much larger than
available memory. We will cover streaming algorithms and sketching methods
that produce compact data structures, dimension reduction methods that
preserve geometric structure, efficient algorithms for numerical linear
algebra, graph sparsification methods, as well as impossibility results for
these techniques.

Tentative Syllabus:

1. Sketching and Streaming algorithms for basic statistics:
   — Distinct elements, heavy hitters,  frequency moments, p-stable sketches
2. Dimension Reduction
   — Johnson Lindenstrauss lemma, lower bounds and impossibility results
3. Graph stream algorithms
   — connectivity, cut/spectral sparsifiers, spanners, matching, graph
4. Lower bounds for Sketching and Streaming:
   — communication complexity: Equality, Index and Set-Disjointness
5. Locality Sensitive Hashing
   — similarity estimation, approximate nearest neighbor search, data
dependent hashing
6. Fast Approximate Numerical Linear Algebra
   — matrix multiplication, low-rank approximation, subspace embeddings,
least squares regression
7. Massively Parallel Computing Models
   — MST, connected components, matching, and submodular optimization in
the MapReduce model

Course website:

Units: 3

3 problems sets (1 can be replaced by programming assignment) and research

Students will be expected to have a strong background in algorithms and
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list