Toolkit for modern algorithms

• Akamai paper: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web (STOC 1997)
• A survey of Algorithmic Nuggets in Content Delivery
• Chord: A scalable peer-to-peer lookup service for internet applications (SIGCOMM 2001)
• Dynamo: Amazon’s highly available key-value store (SOSP 2007)
• Rendezvous hashing: A name-based mapping scheme for Rendezvous (Nov, 1996)

• Network applications of Bloom filters: A survey (Broder and Mitzenmacher, 2005)
• An improved data stream summary: The count-min sketch and its applications (Cormode and Muthukrishnan, 2003)

Mathematical analysis of balls in bins (uniform + two choices):

• Lecture notes from CMU course (A. Gupta, CMU)

• k-d trees on Wikipedia
• Python implementation
• ANN: A library for approximate NNS
• Splitting rule with a rigorous analysis: It’s okay to be skinny if your friends are fat (Maneewongvatana and Mount, 1999)

Intrisinc dimensionality:

• Navigating nets (Krauthgamer and Lee, 2003)
• Cover trees - paper and implementation (Beygelzimer, Kakade, and Langford)
• Fast Construction of Nets in Low Dimensional Metrics, and Their Applications (Har-Peled and Mendel, 2004)
• Nearest-neighbor searching and metric space dimensions (Clarkson, 2005)
• Random projection trees and low-dimensional manifolds (Dasgupta and Freund, 2008)

k-d tree animation:

• Locality sensitive hashing (LSH) (Wikipedia)
• The paper that led to MinHash at Alta Vista: Identify and filtering near-duplicate documents (Broder, 2000)

• Near-optimal hashing algorithms for approximate nearest neighbor in high dimension (Andoni and Indyk, 2008)

• These notes give a short formal proof of the JL lemma: Dimension reduction notes from CSE 525

• Faster dimension reduction (Ailon and Chazelle, 2010)
• Extensions of Lipschitz mappings into a Hilbert space (Johnson and Lindenstrauss, 1984)

We discussed Euclidean dimension reduction based on linear maps. But there are some data sets with low-dimensional structure (for instance, points coming from a manifold) where one wants to do non-linear dimension reduction.

• A theory of the learnable (Valiant, 1984)

• Understanding deep learning requires rethinking generalization (Zhang, et. al., 2017)
  A phenemonon that is currenly not fully explained is the the generalizability of models from deep learning. Often such models are very complex, meaning they should suffer from overfitting. Yet even without explicit regularization, these models generalize unexpectedly well from training data.

• Deep Double Descent: Where bigger models and more data hurt (Nakkiran, et. al., 2019)

• The lessons we learned from a dead fish (Harvard Neuro Blog)
• The spread of evidence-poor medicine via flawed social-network analysis (Russ Lyons, 2011)

• Recovering sparse signals via $\ell_1$ regularization: Candes and Watkin, 2008
  The algorithm described in this survey—also known as “basis pursuit”—is a fundamental building block for compressive sensing.

• A spectral version of $\ell_1$ regularization is useful for Matrix completion and Netflix problem

• A Different Kind of Gene Mapping: Comparing Genetic and Geographic Structure in Europe
• Eigenfaces blog post
• Everything you didn’t know about PCA
• PCA explained visually - possibly useful visualization tools

• Power method still powerful

• Singular value decomposition and applications

• A blog post describing Spearman’s original experiment
• A blog post about the method of moments in research on evolution
• Tensor Decompositions and Applications by Kolda and Bader

• Dan Spielman’s lecture notes for a semester-long course on Spectral Graph Theory.
• For some more advanced material, see these recent courses by Amin Saberi (Stanford) and Shayan Oveis Gharan (UW).
• A general-audience scientific talk I gave on The unreasonable effectiveness of spectral graph theory
• Google’s first ranking algorithm PageRank can be seen as envisioning the web graph as a physical system.
• Anup Rao (CSE professor) advocates using spectral methods to analyze trade networks.
• A little tutorial: Spectral clustering for beginners

• A survey talk of Emmanuel Candes on compressive sensing
• A faster single-pixel camera

• Discussion of the applications in medical imaging

• A video I made in 2005 of the \(\ell_2\) ball morphing into the \(\ell_1\) ball, then into the \(\ell_{\infty}\) ball.
• A CSE 525 lecture on analysis of random sensing matrices

• The effectiveness of convex programming in the information and physical sciences

• A writeup of the probabilistic tools that go into Nate Silver’s political forecasting model
• CSE 525 lecture notes: See lectures on Martingales, concentration inequalities, Markov chains, rapid mixing, and eigenvalues
• Cover time of the 2D torus

• CSE 525 lecture on MCMC
• MCMC “without all the BS”
• The MCMC Revolution (Diaconis)
• Nature article on AlphaGo

• Sections 1-3 of Foundations of Distributed Consensus and Blockchains (Elaine Shi)

• Sections 14 of Foundations of Distributed Consensus and Blockchains (Elaine Shi)
• Lex Friedman interviews Saifdean Ammous about Bitcoin, Anarchy, and Austrian Economics