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