Algorithms
- Negacyclic Polynomial Multiplication
December 9, 2022 - Polynomial Multiplication Using the FFT
November 16, 2022 - "Practical Math" Preview: Collect Sensitive Survey Responses Privately
May 14, 2022 - Searching for RH Counterexamples — Search Strategies
September 28, 2020 - Earthmover Distance
March 5, 2018 - Binary Search on Graphs
November 8, 2017 - Formulating the Support Vector Machine Optimization Problem
June 5, 2017 - The Inner Product as a Decision Rule
May 22, 2017 - Bayesian Ranking for Rated Items
March 13, 2017 - The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm
February 27, 2017 - Zero Knowledge Proofs for NP
August 1, 2016 - The Blum-Blum-Shub Pseudorandom Generator
July 11, 2016 - Zero Knowledge Proofs — A Primer
July 5, 2016 - Singular Value Decomposition Part 2: Theorem, Proof, Algorithm
May 16, 2016 - Singular Value Decomposition Part 1: Perspectives on Linear Algebra
April 18, 2016 - Big Dimensions, and What You Can Do About It
February 8, 2016 - Hashing to Estimate the Size of a Stream
January 4, 2016 - Load Balancing and the Power of Hashing
December 28, 2015 - A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details
November 12, 2015 - Serial Dictatorships and House Allocation
October 26, 2015 - One definition of algorithmic fairness: statistical parity
October 19, 2015 - The Boosting Margin, or Why Boosting Doesn't Overfit
September 21, 2015 - The Welch-Berlekamp Algorithm for Correcting Errors in Data
September 7, 2015 - What does it mean for an algorithm to be fair?
July 13, 2015 - Weak Learning, Boosting, and the AdaBoost algorithm
May 18, 2015 - The Many Faces of Set Cover
May 4, 2015 - Markov Chain Monte Carlo Without all the Bullshit
April 6, 2015 - Finding the majority element of a stream
March 9, 2015 - Hamming's Code
March 2, 2015 - Linear Programming and the Simplex Algorithm
December 1, 2014 - Learning a single-variable polynomial, or the power of adaptive queries
November 18, 2014 - On the Computational Complexity of MapReduce
October 5, 2014 - When Greedy Algorithms are Perfect: the Matroid
August 26, 2014 - Parameterizing the Vertex Cover Problem
August 25, 2014 - When Greedy Algorithms are Good Enough: Submodularity and the (1—1/e)-Approximation
July 7, 2014 - The Mathematics of Secret Sharing
June 23, 2014 - Learning to Love Complex Numbers
May 26, 2014 - Community Detection in Graphs — a Casual Tour
May 19, 2014 - Stable Marriages and Designing Markets
April 2, 2014 - Elliptic Curve Diffie-Hellman
March 31, 2014 - Connecting Elliptic Curves with Finite Fields
March 19, 2014 - Want to make a great puzzle game? Get inspired by theoretical computer science.
March 17, 2014 - Programming with Finite Fields
March 13, 2014 - Elliptic Curves as Python Objects
February 24, 2014 - Simulating a Biased Coin with a Fair Coin
February 12, 2014 - Simulating a Fair Coin with a Biased Coin
February 8, 2014 - Fixing Bugs in "Computing Homology"
January 23, 2014 - The Two-Dimensional Fourier Transform and Digital Watermarking
December 30, 2013 - Adversarial Bandits and the Exp3 Algorithm
November 8, 2013 - Optimism in the Face of Uncertainty: the UCB1 Algorithm
October 28, 2013 - Reservoir Sampling
July 5, 2013 - Guest Post: Torus-Knotted Baklava
June 28, 2013 - Miller-Rabin Primality Test
June 16, 2013 - Bezier Curves and Picasso
May 11, 2013 - Computing Homology
April 10, 2013 - Seam Carving for Content-Aware Image Scaling
March 4, 2013 - k-Means Clustering and Birth Rates
February 4, 2013 - Depth- and Breadth-First Search
January 22, 2013 - Neural Networks and the Backpropagation Algorithm
December 9, 2012 - Decision Trees and Political Party Classification
October 8, 2012 - Complete Sequences and Magic Tricks
October 2, 2012 - Trees—A Primer
September 16, 2012 - K-Nearest-Neighbors and Handwritten Digit Classification
August 26, 2012 - The Cellular Automaton Method for Cave Generation
July 29, 2012 - Dynamic Time Warping for Sequence Comparison
July 25, 2012 - The Fast Fourier Transform
July 18, 2012 - Principal Component Analysis
June 28, 2012 - Streaming Median
June 14, 2012 - Kolmogorov Complexity—A Primer
April 21, 2012 - Optimally Stacking the Deck—Texas Hold 'Em
April 9, 2012 - Classic Nintendo Games are NP-Hard
March 22, 2012 - In Place Uniform Shuffle
March 18, 2012 - P vs. NP, A Primer (And a Proof Written in Racket)
February 23, 2012 - Cryptanalysis with N-Grams
February 3, 2012 - Word Segmentation, or Makingsenseofthis
January 15, 2012 - A Spoonful of Python (and Dynamic Programming)
January 12, 2012 - Numerical Integration
January 8, 2012 - Row Reduction Over A Field
December 30, 2011 - Metrics on Words
December 19, 2011 - Tiling a Chessboard with Dominoes (Opposite Colors Removed)
November 18, 2011 - A Taste of Racket
October 2, 2011 - The Perceptron, and All the Things it Can't Perceive
August 11, 2011 - Graph Coloring, or Proof by Crayon
July 14, 2011 - Optimally Stacking the Deck—Kicsi Poker
July 11, 2011 - Turing Machines—A Primer
July 4, 2011 - The Wild World of Cellular Automata
June 29, 2011 - Google's Page Rank—The Final Product
June 20, 2011 - Google's PageRank—A First Attempt
June 18, 2011 - Big-O Notation—A Primer
June 14, 2011 - Well Orderings and Search
June 14, 2011 - Google's PageRank—Introduction
June 12, 2011