Media Summary: Communication complexity (indexing, gap hamming) + application to median and F0 lower bounds. Amnesic dynamic programming (approximate distance to monotonicity). Randomized and approximate F0 lower bounds, disjointness, Fp lower bound, dimensionality reduction (JL lemma).
Algorithms For Big Data Compsci 229r Lecture 9 - Detailed Analysis & Overview
Communication complexity (indexing, gap hamming) + application to median and F0 lower bounds. Amnesic dynamic programming (approximate distance to monotonicity). Randomized and approximate F0 lower bounds, disjointness, Fp lower bound, dimensionality reduction (JL lemma). MapReduce: TeraSort, minimum spanning tree, triangle counting. External memory model: linked list, matrix multiplication, B-tree, buffered repository tree, sorting. P-stable sketch analysis, Nisan's PRG, ℓp estimation for p
Low-rank approximation, column-based matrix reconstruction, k-means, compressed sensing. Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma. Randomized paging, packing/covering linear programs, weak duality, approximate complementary slackness, primal/dual online ... Power of random signs: ℓ2 norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point ... Learning from experts, multiplicative weights.
