Takashi's Notes
Search
Search
Dark mode
Light mode
Explorer
Home
❯
courses
❯
algorithms for big data
Folder: courses/algorithms-for-big-data
25 items under this folder.
May 02, 2026
distinct elements, k-wise independence, geometric subsampling of streams
May 02, 2026
necessity of randomized/approximate guarantees, linear sketching, AMS sketch, p-stable sketch 0<p<2
May 02, 2026
p-stable sketch analysis, Nisan's PRG, high ℓp norms (p>2) via max-stability
May 02, 2026
analysis of ℓp estimation algorithm via max-stability, deterministic point query via incoherent matrices
May 02, 2026
CountMin sketch, point query, heavy hitters, sparse approximation
May 02, 2026
amnesic dynamic programming (approximate distance to monotonicity)
May 02, 2026
communication complexity (indexing, gap hamming) + application to median and F0 lower bounds
May 02, 2026
randomized and approximate F0 lower bounds, disjointness, Fp lower bound, dimensionality reduction (JL lemma)
May 02, 2026
Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma
May 02, 2026
Alon's JL lower bound, beyond worst case analysis: suprema of gaussian processes, Gordon's theorem
May 02, 2026
ORS theorem (distributional JL implies Gordon's theorem), sparse JL
May 02, 2026
sparse JL proof wrap-up, Fast JL Transform, approximate nearest neighbor
May 02, 2026
approximate matrix multiplication with Frobenius error via sampling / JL, matrix median trick, subspace embeddings
May 02, 2026
linear least squares via subspace embeddings, leverage score sampling, non-commutative Khintchine, oblivious subspace embeddings
May 02, 2026
oblivious subspace embeddings, faster iterative regression, sketch-and-solve regression
May 02, 2026
low-rank approximation, column-based matrix reconstruction, k-means, compressed sensing
May 02, 2026
RIP and connection to incoherence, basis pursuit, Krahmer-Ward theorem
May 02, 2026
L1 & L1 recovery, RIP1, unbalanced expanders, Sequential Sparse Matching Pursuit
May 02, 2026
external memory model: linked list, matrix multiplication, B-tree, buffered repository tree, sorting
May 02, 2026
competitive paging, cache-oblivious algorithms: matrix multiplication, self-organizing linked list, static B-tree, lazy funnelsort
May 02, 2026
MapReduce: TeraSort, minimum spanning tree, triangle counting
Apr 13, 2026
logistics, course topics, basic tail bounds (Markov, Chebyshev, Chernoff, Bernstein), Morris' algorithm
Nov 20, 2025
CountSketch, ℓ0 sampling, graph sketching
Nov 20, 2025
Krahmer-Ward proof, Iterative Hard Thresholding
Nov 20, 2025
matrix completion